Subsets & Backtracking

What you'll learn

• The Golden Rule

  When do you reach for backtracking? Use backtracking when you need to: 1. Generate ALL valid configurations (subsets, permutations, combinations) 2. Find ONE valid configuration under constraints (N-Queens, Sudoku) The problem always inv…

• The Core Template

  Every backtracking solution follows this skeleton: The three steps -- choose, explore, unchoose -- form the heartbeat of every problem in this chapter. ---

• The Decision Tree

  Every backtracking problem can be visualized as a decision tree. At each node, you make a choice that branches into sub-problems. For generating subsets of [1, 2, 3]: Each leaf is one subset. The tree has 2^n leaves because each element…

• Two Common Solution-Space Tree Patterns

  Not all decision trees look the same. Backtracking problems fall into two structural patterns based on how choices branch at each level: 1. Multi-Branch Pattern (Combinations/Permutations) At each level of the tree, iterate over a set of…

• Complexity Derivation

  For a tree with branching factor b and depth n, the total number of nodes is: This geometric series is dominated by the last term (the leaf level), so the overall complexity is O(b^n). For the binary decision pattern, b = 2. For permutat…

• Systematic Framework for Structuring Any Backtracking Solution

  When faced with a new backtracking problem, work through these five identification steps before writing code: 1. Identify what each "level" of the tree represents. Usually one position or one element in the input (e.g., level i = decidin…

• Pattern 1: Subsets (Power Set)

  Problem: Given a set of distinct integers, return all possible subsets. Key insight: For each element, make a binary choice -- include it or skip it.

• Approach A: Recursive (Include/Exclude)

• Approach B: Iterative (Cascading)

  Start with an empty set. For each number, take every existing subset and create a new one by adding the current number. Step-by-step for [1, 2, 3]:

• Approach C: Index-based Backtracking

  This approach collects subsets at every node (not just leaves), and uses the start parameter to avoid revisiting earlier elements. ---

• Pattern 2: Subsets with Duplicates

  Problem: Given integers that may contain duplicates, return all unique subsets. Key insight: Sort the input first. Then at each decision level, skip elements that are the same as a previously processed element at that same level.

• Why Sorting Enables Duplicate Detection

  Without sorting, duplicates could appear anywhere and detecting "have I already tried this value at this position?" would require a set at each level. Sorting groups identical values together, so a simple "is this the same as the previou…

• Pattern 3: Permutations

  Problem: Given distinct integers, return all possible orderings. Key insight: Unlike subsets where order does not matter, permutations require every element to appear exactly once, in every possible position. This yields n! results.

• Approach A: Used-tracking

• Approach B: Swap-based

  Instead of building a new list, swap elements into position:

• Recursion Tree for [1, 2, 3]

  6 leaves = 3! = 6 permutations. ---

• Pattern 4: Permutations with Duplicates

  Problem: Given integers that may contain duplicates, return all unique permutations. Key insight: Sort first. At each position, skip a value if the same value was already placed at this position and was subsequently undone (backtracked).…

• Pattern 5: Combinations (Choose k from n)

  Problem: Given n and k, return all combinations of k numbers from 1 to n. Key insight: Like subsets, but only collect when we have exactly k elements. Order does not matter -- [1,2] and [2,1] are the same combination.

• Pruning Optimization

  If the remaining elements are fewer than what we still need, we can stop early: This pruning can eliminate large branches of the tree when n is much larger than k. ---

• Pattern 6: Combination Sum

  Problem: Given candidates and a target, find all combinations that sum to the target. Each candidate may be used unlimited times. Key insight: Unlike basic combinations, we pass the same index (not index + 1) to allow reuse of the curren…

• Pattern 7: Letter Combinations of Phone Number

  Problem: Given a digit string, return all possible letter combinations (like T9 phone mapping). Key insight: Each digit maps to 3-4 letters. This is multi-branch recursion where the branching factor varies per level. Decision tree for "2…

• Pattern 8: Generate Parentheses

  Problem: Generate all valid combinations of n pairs of parentheses. Key insight: This is constraint-based generation. At each step, you can add '(' if you have not used all of them, and ')' only if the number of closing brackets is less…

• Pattern 9: Word Search on Grid

  Problem: Given a 2D grid of characters and a word, determine if the word exists by following adjacent cells (no cell reused). Key insight: DFS from each cell + backtracking the "visited" state. This is backtracking on a grid rather than…

• Pattern 10: N-Queens

  Problem: Place n queens on an n x n board so no two queens threaten each other. Key insight: Place one queen per row. Track which columns and diagonals are already attacked. Backtrack when no safe column exists for the current row. Why r…

• Complexity Analysis

  | Pattern | Time Complexity | Space Complexity | |---------|----------------|-----------------| | Subsets | O(n 2^n) | O(n) recursion depth | | Subsets with dups | O(n 2^n) worst case | O(n) | | Permutations | O(n n!) | O(n) | | Permu…

• Decision Table: When to Use Which Pattern

  ---

• Common Pitfalls

  1. Forgetting to copy: Storing a reference to the mutable current list instead of a copy means all results point to the same (empty) list after backtracking completes. 2. Not undoing the choice: If you forget current.pop() or the equival…

• Template Summary

  ---

• Optimization Techniques

• 1. Sort + Early Termination

  For combination sum problems, sorting candidates allows you to break out of the loop early when the current candidate exceeds the remaining target:

• 2. Constraint Propagation

  In problems like Sudoku or N-Queens, maintain data structures (sets, bitmasks) that allow O(1) validity checking rather than scanning the board.

• 3. Bitmask Representation

  For subset generation, each subset can be represented as a bitmask of n bits: This iterative approach avoids recursion overhead entirely. ---

• Backtracking vs Dynamic Programming

  | Aspect | Backtracking | Dynamic Programming | |--------|-------------|-------------------| | Goal | Enumerate all solutions or find one valid solution | Find optimal (min/max) value or count | | Overlapping subproblems? | Usually no (e…