Skip to content
DSA recursion 12 min read

Recursion & Backtracking Exercises: Answer Sheet & Solutions

This is the answer sheet for the recursion & backtracking exercises. Each solution gives the key idea, the optimal complexity, the code in all four languages (use the switcher), and a common pitfall. Try the problems first — then check your work here.

Q1. Factorial

Idea: n! = n × (n-1)!, with the base case 0! = 1! = 1. Use an inclusive n <= 1 guard so 0 is handled too.

Complexity: O(n) time, O(n) space (the recursion holds n stack frames).

long long factorial(int n) {
    if (n <= 1) return 1;            // base case
    return n * factorial(n - 1);     // recursive case
}

Pitfall: Using n == 1 as the only base case infinite-loops (or errors) on n = 0. Use n <= 1. Also, n! overflows 64-bit integers past n = 20 — use a big-integer type for large n.

Q2. Sum of digits

Idea: The last digit is n % 10; the remaining number is n / 10. Sum the last digit with the recursive sum of the rest. Base case: a single-digit (or zero) number is its own sum.

Complexity: O(d) time and space, where d is the number of digits (≈ log₁₀ n).

int sumDigits(int n) {
    if (n < 10) return n;                  // base case: single digit
    return n % 10 + sumDigits(n / 10);     // last digit + rest
}

Pitfall: In JavaScript, n / 10 is floating-point — you must Math.floor it, or the recursion never reaches a single digit. C++/Java integer division and Python // truncate automatically.

Q3. Fast power

Idea: Exponentiation by squaring. x^n = (x^(n/2))² when n is even, and x · (x^(n/2))² when odd. Halving n each step gives logarithmic depth. Compute the half once and reuse it.

Complexity: O(log n) time, O(log n) stack space.

double power(double x, int n) {
    if (n == 0) return 1.0;                // base case
    double half = power(x, n / 2);         // compute once
    return (n % 2 == 0) ? half * half : half * half * x;
}

Pitfall: Calling power(x, n/2) twice in the return turns it back into O(n) (actually O(n) calls). Store the half in a variable and square it. (For negative n, compute 1 / power(x, -n).)

Q4. Generate all subsets

Idea: For each element make a binary choice — include it or skip it — then recurse on the next index. At the end of the array, record a copy of the current subset.

Complexity: O(n · 2ⁿ) time (2ⁿ subsets, O(n) to copy each), O(n) stack depth.

void subsets(const std::vector<int>& nums, int i,
             std::vector<int>& cur, std::vector<std::vector<int>>& out) {
    if (i == (int)nums.size()) { out.push_back(cur); return; }
    cur.push_back(nums[i]);                  // include
    subsets(nums, i + 1, cur, out);
    cur.pop_back();                          // skip
    subsets(nums, i + 1, cur, out);
}

Pitfall: Appending cur directly (not a copy) stores a reference to the one shared buffer, so every saved subset ends up identical (and empty) once recursion unwinds. Always snapshot with a copy.

Q5. Generate all permutations

Idea: Backtracking. At each position try every element not yet used; mark it used, recurse, then un-mark it. Record a copy when the current ordering is full-length.

Complexity: O(n · n!) time, O(n) stack depth plus the used array.

void permute(std::vector<int>& nums, std::vector<bool>& used,
             std::vector<int>& cur, std::vector<std::vector<int>>& out) {
    if (cur.size() == nums.size()) { out.push_back(cur); return; }
    for (int i = 0; i < (int)nums.size(); i++) {
        if (used[i]) continue;
        used[i] = true; cur.push_back(nums[i]);
        permute(nums, used, cur, out);
        used[i] = false; cur.pop_back();
    }
}

Pitfall: Forgetting to reset used[i] = false (or to pop cur) on the way back up corrupts later branches — you’ll get missing or duplicated permutations. Every CHOOSE needs a matching UN-CHOOSE.

Q6. Generate parentheses

Idea: Build the string character by character, tracking how many ( and ) remain. You may add ( while opens are left, and ) only while closes left exceed opens left (otherwise the prefix is invalid). That condition prunes every malformed branch.

Complexity: O(4ⁿ / √n) — the nth Catalan number of valid strings, each length 2n.

void gen(int open, int close, std::string& cur, std::vector<std::string>& out) {
    if (open == 0 && close == 0) { out.push_back(cur); return; }
    if (open > 0) { cur.push_back('('); gen(open - 1, close, cur, out); cur.pop_back(); }
    if (close > open) { cur.push_back(')'); gen(open, close - 1, cur, out); cur.pop_back(); }
}
// call: gen(n, n, cur, out);

Pitfall: Allowing ) whenever closes remain (instead of only when close > open) generates invalid strings like ")(". The close > open guard is the whole trick — it keeps every prefix balanced.

Q7. Merge sort

Idea: Divide and conquer: split the array in half, sort each half recursively, then merge the two sorted halves with a two-pointer scan. The merge is what produces the sorted order.

Complexity: O(n log n) time, O(n) extra space for the merged buffers.

std::vector<int> mergeSort(std::vector<int> a) {
    if (a.size() <= 1) return a;
    int mid = a.size() / 2;
    std::vector<int> L = mergeSort({a.begin(), a.begin() + mid});
    std::vector<int> R = mergeSort({a.begin() + mid, a.end()});
    std::vector<int> out; int i = 0, j = 0;
    while (i < (int)L.size() && j < (int)R.size())
        out.push_back(L[i] <= R[j] ? L[i++] : R[j++]);
    while (i < (int)L.size()) out.push_back(L[i++]);
    while (j < (int)R.size()) out.push_back(R[j++]);
    return out;
}

Pitfall: Using < instead of <= in the merge comparison makes the sort unstable (it can reorder equal elements). Use <= to keep equal keys in their original order — important when sorting records by one field.

That’s the full answer sheet. Back to the recursion exercises or continue to sorting.

Last updated June 25, 2026
Was this helpful?