Recursion and Backtracking Master Recap — Templates, Pattern Cues, and Top 30 Problems

Input:  Any "generate all", "find all valid", "count arrangements" problem
Output: A working backtracking implementation in roughly 15 lines

class Solution:
    # 1. Subsets — include or exclude each element
    def subsets(self, nums):
        result = []
        def bt(start, current):
            result.append(current[:])
            for i in range(start, len(nums)):
                current.append(nums[i])
                bt(i + 1, current)
                current.pop()
        bt(0, [])
        return result
 
    # 2. Permutations — used array, every element a candidate at every slot
    def permute(self, nums):
        result, used = [], [False] * len(nums)
        def bt(current):
            if len(current) == len(nums):
                result.append(current[:])
                return
            for i in range(len(nums)):
                if used[i]:
                    continue
                used[i] = True
                current.append(nums[i])
                bt(current)
                current.pop()
                used[i] = False
        bt([])
        return result
 
    # 3. Combination Sum — sort, prune by remaining, allow reuse via i not i+1
    def combinationSum(self, candidates, target):
        candidates.sort()
        result = []
        def bt(start, current, remaining):
            if remaining == 0:
                result.append(current[:])
                return
            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    break  # sorted, so all later candidates are too large
                current.append(candidates[i])
                bt(i, current, remaining - candidates[i])  # i for reuse
                current.pop()
        bt(0, [], target)
        return result
 
    # 4. N-Queens — column and diagonal sets prune O(n!) to manageable
    def nQueens(self, n):
        result = []
        cols, d1, d2 = set(), set(), set()
        board = [['.'] * n for _ in range(n)]
        def bt(r):
            if r == n:
                result.append([''.join(row) for row in board])
                return
            for c in range(n):
                if c in cols or (r - c) in d1 or (r + c) in d2:
                    continue
                board[r][c] = 'Q'
                cols.add(c); d1.add(r - c); d2.add(r + c)
                bt(r + 1)
                board[r][c] = '.'
                cols.discard(c); d1.discard(r - c); d2.discard(r + c)
        bt(0)
        return result

// 1. Subsets
var subsets = function(nums) {
    const result = [];
    const bt = (start, current) => {
        result.push([...current]);
        for (let i = start; i < nums.length; i++) {
            current.push(nums[i]);
            bt(i + 1, current);
            current.pop();
        }
    };
    bt(0, []);
    return result;
};
 
// 2. Permutations
var permute = function(nums) {
    const result = [];
    const used = new Array(nums.length).fill(false);
    const bt = (current) => {
        if (current.length === nums.length) {
            result.push([...current]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.push(nums[i]);
            bt(current);
            current.pop();
            used[i] = false;
        }
    };
    bt([]);
    return result;
};
 
// 3. Combination Sum
var combinationSum = function(candidates, target) {
    candidates.sort((a, b) => a - b);
    const result = [];
    const bt = (start, current, remaining) => {
        if (remaining === 0) {
            result.push([...current]);
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) break;
            current.push(candidates[i]);
            bt(i, current, remaining - candidates[i]);
            current.pop();
        }
    };
    bt(0, [], target);
    return result;
};