Learn DSA Part 7: Recursion and Backtracking - Subsets, Permutations and N-Queens

Recursion is the idea of solving a problem by solving smaller copies of the same problem. Backtracking builds on it to explore every possible choice systematically: all subsets, all permutations, every valid board arrangement. Together they underpin trees, graphs, divide and conquer, and dynamic programming, so getting comfortable here pays off in every later part.

This is Part 7 of the Learn DSA series. We cover how recursion works on the call stack, how to think recursively, the universal backtracking template, pruning, and the complexities interviewers expect you to state. Code is in C++ and Java.

1. How recursion works

Every recursive function has two parts:

• Base case: the smallest input, answered directly without recursion. Missing or wrong base cases cause infinite recursion and a stack overflow.
• Recursive case: express the answer using the answer for a smaller input, and trust that the recursive call returns the right thing.

Each call gets its own stack frame holding its parameters and local variables. Frames pile up until a base case returns, then unwind in reverse order. So recursion uses O(depth) extra space even if it allocates nothing else.

To find the running time, draw the recursion tree: total work is the number of calls times the work per call. A function that calls itself twice on n - 1 creates about 2^n calls; one that calls itself once on n / 2 makes only log n calls (see Part 1).

2. How to think recursively

Ask three questions:

1. What does my function return for an input of size n? Write that down as a sentence.
2. If I already had the answer for a smaller input, how would I build the answer for n?
3. What is the smallest input I can answer directly?

For example, "the height of a tree is 1 + the larger of the heights of its two subtrees, and an empty tree has height 0". This "leap of faith" is exactly how tree problems are solved in Part 9.

3. The backtracking template: choose, explore, un-choose

Backtracking builds a solution step by step. At each step it tries every available choice, recurses to complete the solution, and then undoes the choice before trying the next one. The undo step is what lets a single shared list represent every partial solution.

// All subsets of nums. O(n * 2^n)
void backtrack(const vector<int>& nums, int i, vector<int>& cur,
               vector<vector<int>>& res) {
    if (i == (int)nums.size()) { res.push_back(cur); return; } // copy
    cur.push_back(nums[i]);            // choose: include nums[i]
    backtrack(nums, i + 1, cur, res);  // explore
    cur.pop_back();                    // un-choose
    backtrack(nums, i + 1, cur, res);  // explore without nums[i]
}
vector<vector<int>> subsets(const vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> cur;
    backtrack(nums, 0, cur, res);
    return res;
}

// All subsets of nums. O(n * 2^n)
static void backtrack(int[] nums, int i, List<Integer> cur,
                      List<List<Integer>> res) {
    if (i == nums.length) { res.add(new ArrayList<>(cur)); return; } // copy
    cur.add(nums[i]);                  // choose: include nums[i]
    backtrack(nums, i + 1, cur, res);  // explore
    cur.remove(cur.size() - 1);        // un-choose
    backtrack(nums, i + 1, cur, res);  // explore without nums[i]
}
static List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}

Generating subsets is the simplest example: at each index, either include the element or not. Note that the result stores a copy of the current list; storing the list itself would leave you with empty lists after all the undoing.

Permutations use the same template, but each step may choose any unused element, tracked with a boolean used array:

// All permutations of distinct numbers. O(n * n!)
void permute(const vector<int>& a, vector<bool>& used, vector<int>& cur,
             vector<vector<int>>& res) {
    if (cur.size() == a.size()) { res.push_back(cur); return; }
    for (int i = 0; i < (int)a.size(); i++) {
        if (used[i]) continue;
        used[i] = true;  cur.push_back(a[i]);    // choose
        permute(a, used, cur, res);              // explore
        cur.pop_back();  used[i] = false;        // un-choose
    }
}

// All permutations of distinct numbers. O(n * n!)
static void permute(int[] a, boolean[] used, List<Integer> cur,
                    List<List<Integer>> res) {
    if (cur.size() == a.length) { res.add(new ArrayList<>(cur)); return; }
    for (int i = 0; i < a.length; i++) {
        if (used[i]) continue;
        used[i] = true;  cur.add(a[i]);          // choose
        permute(a, used, cur, res);              // explore
        cur.remove(cur.size() - 1);  used[i] = false;   // un-choose
    }
}

4. Pruning: cutting off hopeless branches

Pure backtracking explores everything, so it is exponential. Pruning stops exploring a branch as soon as it cannot lead to a valid answer, and it often makes the difference between passing and timing out.

• Combination Sum: sort the candidates; once a candidate exceeds the remaining target, every later one does too, so break the loop.
• Avoiding duplicates (Subsets II, Permutations II): sort the input and skip a value if it equals the previous one at the same recursion level.
• N-Queens: keep sets of used columns and diagonals so each placement check is O(1), and only place queens in safe squares.

// Count N-Queens solutions with O(1) safety checks
int n, cnt = 0;
vector<bool> col, d1, d2;   // sizes n, 2n, 2n
void place(int r) {
    if (r == n) { cnt++; return; }
    for (int c = 0; c < n; c++) {
        if (col[c] || d1[r - c + n] || d2[r + c]) continue;   // prune
        col[c] = d1[r - c + n] = d2[r + c] = true;
        place(r + 1);
        col[c] = d1[r - c + n] = d2[r + c] = false;
    }
}
int totalNQueens(int size) {
    n = size; cnt = 0;
    col.assign(n, false); d1.assign(2 * n, false); d2.assign(2 * n, false);
    place(0);
    return cnt;
}

// Count N-Queens solutions with O(1) safety checks
static int n, cnt;
static boolean[] col, d1, d2;   // sizes n, 2n, 2n
static void place(int r) {
    if (r == n) { cnt++; return; }
    for (int c = 0; c < n; c++) {
        if (col[c] || d1[r - c + n] || d2[r + c]) continue;   // prune
        col[c] = d1[r - c + n] = d2[r + c] = true;
        place(r + 1);
        col[c] = d1[r - c + n] = d2[r + c] = false;
    }
}
static int totalNQueens(int size) {
    n = size; cnt = 0;
    col = new boolean[n]; d1 = new boolean[2 * n]; d2 = new boolean[2 * n];
    place(0);
    return cnt;
}

On the diagonals, every cell with the same row - col lies on one diagonal and every cell with the same row + col lies on the other. Adding n keeps the index non-negative.

5. Complexity of common backtracking problems

The extra factor of n in the first two rows comes from copying each result of length up to n. Mention this in interviews; it shows you understand where the time goes.

6. Common mistakes

• Forgetting to undo the choice (pop the element, unmark visited, restore the board).
• Storing a reference instead of a copy of the current path in the result.
• Wrong base case, especially off-by-one on indices, causing missing or duplicate answers.
• Very deep recursion on large inputs (for example 10^5 levels) can overflow the stack; use an explicit stack or an iterative approach.
• Recomputing the same subproblems: if the recursion tree repeats states, add memoization.

Practice problems

These are classic LeetCode-style problems, listed from easy to hard. For each backtracking problem, write down the choice made at each step before coding.

1. Fibonacci Number (easy)
2. Pow(x, n) (medium, fast exponentiation)
3. Subsets (medium)
4. Subsets II (medium, duplicates)
5. Permutations (medium)
6. Permutations II (medium, duplicates)
7. Combinations (medium)
8. Combination Sum (medium)
9. Letter Combinations of a Phone Number (medium)
10. Generate Parentheses (medium)
11. Palindrome Partitioning (medium)
12. Word Search (medium)
13. N-Queens (hard)
14. Sudoku Solver (hard)