Recursion and Backtracking

Backtracking is recursion that explores choices and undoes them: choose, explore, un-choose. One template solves subsets, permutations, combinations, puzzles and grid searches. Interviewers check that you can apply it cleanly and explain the exponential cost.

1. How do you think about any recursive problem?

Define what the function returns for a given input, write the base case (smallest input), and express the answer using smaller calls — trusting that they work. Then check that every path moves towards the base case. Draw the recursion tree to estimate the complexity.

2. Generate all subsets of a set.

At each index choose to include or skip the element. There are 2ⁿ subsets, so the time is O(n · 2ⁿ).

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}
void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));                // every path is a subset
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);                         // choose
        backtrack(nums, i + 1, path, res);         // explore
        path.remove(path.size() - 1);              // un-choose
    }
}

3. Generate all permutations.

Choose an unused element for each position, mark it used, recurse, then unmark. n! permutations, O(n · n!) time.

List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    dfs(nums, new boolean[nums.length], new ArrayList<>(), res);
    return res;
}
void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true; path.add(nums[i]);
        dfs(nums, used, path, res);
        used[i] = false; path.remove(path.size() - 1);
    }
}

4. Combination sum: combinations that add up to a target (numbers reusable).

Same template; pass i (not i + 1) to allow reuse, and stop early when the remaining target goes below zero. Sorting first allows breaking out of the loop sooner.

void combine(int[] cands, int start, int remain, List<Integer> path, List<List<Integer>> res) {
    if (remain == 0) { res.add(new ArrayList<>(path)); return; }
    for (int i = start; i < cands.length && cands[i] <= remain; i++) {   // cands sorted
        path.add(cands[i]);
        combine(cands, i, remain - cands[i], path, res);                // i: reuse allowed
        path.remove(path.size() - 1);
    }
}

5. Solve N-Queens.

Place one queen per row; for each column check that the column and both diagonals are free (track them in sets or boolean arrays), recurse to the next row, then remove the queen. Pruning keeps it far below n^n.

int totalNQueens(int n) {
    return place(0, n, new boolean[n], new boolean[2 * n], new boolean[2 * n]);
}
int place(int row, int n, boolean[] cols, boolean[] d1, boolean[] d2) {
    if (row == n) return 1;
    int count = 0;
    for (int c = 0; c < n; c++) {
        if (cols[c] || d1[row + c] || d2[row - c + n]) continue;
        cols[c] = d1[row + c] = d2[row - c + n] = true;
        count += place(row + 1, n, cols, d1, d2);
        cols[c] = d1[row + c] = d2[row - c + n] = false;
    }
    return count;
}

6. Search for a word in a grid of letters.

DFS from each cell matching the first letter; mark the cell as visited while exploring its four neighbours, and unmark it when backtracking.

boolean exist(char[][] b, String word) {
    for (int r = 0; r < b.length; r++)
        for (int c = 0; c < b[0].length; c++)
            if (dfs(b, word, 0, r, c)) return true;
    return false;
}
boolean dfs(char[][] b, String w, int k, int r, int c) {
    if (k == w.length()) return true;
    if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] != w.charAt(k)) return false;
    char saved = b[r][c];
    b[r][c] = '#';                                                 // mark visited
    boolean found = dfs(b, w, k + 1, r + 1, c) || dfs(b, w, k + 1, r - 1, c)
                 || dfs(b, w, k + 1, r, c + 1) || dfs(b, w, k + 1, r, c - 1);
    b[r][c] = saved;                                               // backtrack
    return found;
}

7. How do you avoid duplicate results when the input has duplicates?

Sort the input, then at the same recursion level skip an element equal to the previous one: if (i > start && nums[i] == nums[i - 1]) continue;. For permutations, also require the previous duplicate to be used.

8. When does recursion become dynamic programming?

When the same subproblems repeat — the recursion tree has identical branches — caching results (memoisation) turns exponential time into polynomial. Backtracking problems that must list every solution stay exponential; counting or optimising problems often become DP.