Backtracking

Build candidates one choice at a time, undo the choice, try the next.

Reach for it when

Generate all subsets, permutations, combinations, partitions
Constraint satisfaction (N-Queens, Sudoku, word search)
Small n (usually 20 or less)

Core idea

Explore a decision tree with DFS. At each level, choose an option, recurse, then undo the choice so the shared state is clean for the next option. Prune branches as early as a constraint fails; that pruning is what makes exponential searches practical.

Template · Exponential: O(2^n) subsets, O(n!) permutations

def subsets(nums):
    res, path = [], []
    def dfs(i):
        if i == len(nums):
            res.append(path[:])     # copy!
            return
        path.append(nums[i])        # choose
        dfs(i + 1)
        path.pop()                  # undo
        dfs(i + 1)                  # skip
    dfs(0)
    return res

vector<vector<int>> subsets(const vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> path;
    function<void(int)> dfs = [&](int i) {
        if (i == (int)nums.size()) { res.push_back(path); return; }  // copies path
        path.push_back(nums[i]);   // choose
        dfs(i + 1);
        path.pop_back();           // undo
        dfs(i + 1);                // skip
    };
    dfs(0);
    return res;
}

Common pitfalls

Appending path instead of a copy of path
Duplicates: sort first and skip equal siblings
Forgetting to undo state (visited marks, path) after recursion

Practice · 0 / 10 done

Combination SumMedium
Combination Sum IIMedium
Generate ParenthesesMedium
Letter Combinations of a Phone NumberMedium
Palindrome PartitioningMedium
PermutationsMedium
SubsetsMedium
Subsets IIMedium
Word SearchMedium
N QueensHard