Category: Recursion Problem

Recursion Problem

How Many Binary Search Trees With N Nodes

Tech CornerLeave a comment

Problem

How Many Binary Search Trees With N Nodes

Write a function that returns the number of distinct binary search trees that can be constructed with n nodes. For the purpose of this exercise, do solve the problem using recursion first even if you see some non-recursive approaches.

Example

{
"n": 3
}

Output:

5

Solution

function how_many_bsts(n) {
    
    if (n === 0) {
        return 1;
    }

    let result = 0;

    for (let i = 1; i <= n; i++) {
        result += how_many_bsts(i - 1) * how_many_bsts(n - i);
    }

    return result;
}

Time and Space Complexity


Time: O(Catalan number(n)).
Auxiliary space: O(n).
Total space: O(n).
Recursion Problem

Palindromic Decomposition Of A String

Tech CornerLeave a comment

Problem

Find all palindromic decompositions of a given string s.

A palindromic decomposition of string is a decomposition of the string into substrings, such that all those substrings are valid palindromes.

Example

{
"s": "abracadabra"
}

Output:

["a|b|r|a|c|ada|b|r|a", "a|b|r|aca|d|a|b|r|a", "a|b|r|a|c|a|d|a|b|r|a"]

Solution

function is_palindrome(s, l, r) {
    while (l < r) {
        if (s[l++] != s[r--]) return false;
    }
    return true;
}

function dfs(decompositions_container, s, pos, cur_decomposition) {
    // If we have reached the end, add the string.
    let n = s.length;
    if (pos == n) {
        decompositions_container.push(cur_decomposition);
        return decompositions_container;
    }
    // Try to add s[pos, i] if it a palindrome.
    for (let i = pos; i < n; i++) {
        if (is_palindrome(s, pos, i)) {
            if (pos == 0) {
                // We are adding s[0, i] so do not put '|' before it.
                dfs(decompositions_container, s, i + 1,
                    s.substr(pos, i - pos + 1, n));
            }
            else {
                dfs(decompositions_container, s, i + 1,
                    cur_decomposition + '|' + s.substr(pos, i - pos + 1));
            }
        }
    }
}

function generate_palindromic_decompositions(s) {

    let decompositions_container = [];

    dfs(decompositions_container, s, 0, "");
    
    return decompositions_container;
}

generate_palindromic_decompositions('abracadabra');

Time and Space Complexity


Time: O(2^(n-1) * n).
Auxiliary space: O(2^(n-1) * n).
Total space: O(2^(n-1) * n).
Recursion · Recursion Problem

Generate All Subsets Of A Set

Tech CornerLeave a comment

Problem

Generate ALL possible subsets of a given set. The set is given in the form of a string s containing distinct lowercase characters ‘a’ – ‘z’.

Example

{
"s": "xy"
}

Output:

["", "x", "y", "xy"]

Solution

function subset(inputStr) {
    let allsubset = [""];

    for (let i = 1; i <= inputStr.length; i++) {
        let old_len = allsubset.length;
        for (let j = 0; j < old_len; j++) {
            // Note that we are doing push that is adding value at the end of array, so we already have the old values stored in it.
            allsubset.push(allsubset[j] + inputStr[i - 1]);
        }
    }
    return allsubset;
}

subset("xy");

Time and Space Complexity


Time: O(2^n * n).
Auxiliary space: O(2^n * n).
Total space: O(2^n * n).
Recursion Problem

Recursion Power

Tech CornerLeave a comment

Problem

Given a base a and an exponent b. Your task is to find ab. The value could be large enough. So, calculate ab % 1000000007.

Example One

{
"a": 2,
"b": 10
}

Output:

1024

Solution

function power(base, exponent) {
  if (exponent === 1) {
    return base;
  } else {
    return base * power(base ,exponent-1);
  }
}

Time and Space Complexity


Time: O(b).
Auxiliary space: O(1).
Total space: O(1).