2.5 Backtracking — DSA Crash Course

Deep Dive: The Decision Tree You Are Walking

Beginner tip: Backtracking is like trying on outfits. You pick a shirt, then try pants to go with it. If nothing works, you put the shirt back (backtrack) and try the next one. The key steps are: choose (pick an option), explore (see if it leads to a solution), un-choose (put it back if it did not work). This pattern solves any "generate all valid combinations" problem.

Subsets: Include or Exclude

For nums = [1, 2, 3], the decision tree:

                    []
                /         \
          include 1      skip 1
            [1]            []
          /     \        /     \
     incl 2  skip 2  incl 2  skip 2
      [1,2]   [1]    [2]      []
      / \     / \    / \     / \
   +3  -3  +3  -3  +3  -3  +3  -3
[1,2,3][1,2][1,3][1][2,3][2] [3] []

8 leaf nodes = 2^3 subsets. Each path from root to leaf is one subset. The backtracking template walks this tree with path.append() (go left) and path.pop() (go right).

Permutations: Choose from Remaining

For nums = [1, 2, 3], each level picks one unused number:

Level 0 (pick 1st):  choose 1    choose 2    choose 3
Level 1 (pick 2nd):  2 or 3      1 or 3      1 or 2
Level 2 (pick 3rd):  remaining   remaining   remaining

Result: [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

6 leaves = 3!. At each level, you have fewer choices because elements are "used."

The Template (Commit, Explore, Undo)

def backtrack(state):
    if goal_reached(state):
        record(state)
        return
    for choice in available_choices(state):
        make_choice(choice)        # COMMIT   (path.append)
        backtrack(updated_state)   # EXPLORE  (recurse deeper)
        undo_choice(choice)        # UNDO     (path.pop)

Pruning = skipping choices early when they cannot lead to valid solutions.

Choose / Explore / Unchoose -- The Decision Tree, Pruned and Unpruned

Subsets of [1, 2, 3] -- the unpruned binary tree. At every level you make a yes/no decision: "include this number?" That gives 2^n leaves, one per subset.

                              []
                  include 1 /     \ skip 1
                          [1]                []
              incl 2 /        \ skip 2     incl 2 /     \ skip 2
                  [1,2]        [1]            [2]            []
            +3 /     \ -3   +3 /  \ -3    +3 /  \ -3     +3 /  \ -3
        [1,2,3] [1,2] [1,3] [1] [2,3] [2]    [3]      []

Leaves (8 = 2^3): [1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []

Every path root -> leaf is one subset. The three-line template walks this tree:

def backtrack(i, path):
    if i == len(nums):
        result.append(path[:])    # CHOOSE was implicit; record the leaf
        return
    path.append(nums[i])          # CHOOSE: include nums[i]
    backtrack(i + 1, path)        # EXPLORE
    path.pop()                    # UNCHOOSE
    backtrack(i + 1, path)        # EXPLORE the "skip" branch

Combination Sum (candidates = [2, 3, 5], target = 8) -- the SAME tree, pruned. Here the branches are "pick a candidate (with reuse)" and we keep a running remaining = target - sum(path). The instant remaining < 0 we cut the whole subtree -- no point exploring deeper, every descendant only adds more.

                              path=[], remaining=8
              pick 2 /       pick 3 |       pick 5 \
            [2], r=6        [3], r=5         [5], r=3
       2/   3|   5\       3/   5\           5\
   [2,2]  [2,3] [2,5]   [3,3]  [3,5]      [5,5]
   r=4    r=3   r=1     r=2    r=0 OK!    r=-2  PRUNED (sum exceeded)
   ...    ...   ...     ...                
   [2,3,3]  r=0 OK!
   [2,2,2,2] r=0 OK!

Without pruning the tree would explode. With pruning we only descend while there is still room in the budget. (Sorting candidates first lets us prune even harder: once c > remaining, every later candidate also exceeds, so break out of the loop.)

The whole pattern in three lines.

choose    -> path.append(c)           # commit to a choice
explore   -> backtrack(next_state)    # recurse with the choice in effect
unchoose  -> path.pop()               # undo, so the next sibling sees a clean slate

Every backtracking solution -- subsets, permutations, N-Queens, Sudoku, Word Search -- is just this trio plus a problem-specific is_goal and pruning rule.

Quick Reference (Cheat Sheet)

Before You Start -- How to Think About Backtracking

What Is Backtracking?

Backtracking = DFS on a decision tree + pruning invalid branches.

You're exploring all possible choices. At each step, you CHOOSE, EXPLORE, then UNCHOOSE (undo).

The Universal Template

def backtrack(candidates, path, result):
    if is_goal(path):             # base case: found a valid solution
        result.append(path[:])    # save a COPY
        return
    for choice in candidates:
        if is_valid(choice, path):  # PRUNE: skip invalid choices
            path.append(choice)     # CHOOSE
            backtrack(next_candidates, path, result)  # EXPLORE
            path.pop()              # UNCHOOSE (backtrack)

Visualize the Decision Tree

Subsets of [1,2,3]:
                    []
              /     |      \
           [1]    [2]     [3]
          /   \     |
       [1,2] [1,3] [2,3]
         |
      [1,2,3]

Each node is a state. Each edge is a choice. Leaves are results.

The Three Backtracking Flavors

Type	Question	Key Difference	Example
Subsets	"Choose any subset"	Include or exclude each element	Subsets, Combination Sum
Permutations	"Arrange all elements"	All orderings matter	Permutations, N-Queens
Partitions	"Split into valid groups"	Every element assigned	Palindrome Partitioning

When You See a Problem, Ask Yourself

1. "All subsets / combinations"? -> Subset pattern (choose from index onwards)
2. "All permutations / arrangements"? -> Permutation pattern (used[] array)
3. "Can reuse elements"? -> Don't advance start index
4. "No duplicates in result"? -> Sort input + skip consecutive duplicates
5. "Constraint-heavy placement" (N-Queens, Sudoku)? -> Heavy pruning

Handling Duplicates

Input: [1, 2, 2] and "no duplicate combinations"
  1. Sort the input
  2. In the loop: if candidates[i] == candidates[i-1] and i > start: skip
  This ensures [1,2] uses the first 2, not the second.

Common Mistakes

Forgetting path[:] (copy) when adding to result -- path is mutable and changes later
Not sorting when the problem says "no duplicate results"
Pruning too aggressively or too little -- trace through small examples

Problems

#	Problem	Variant	Status
1	Subsets	Include/Exclude	[ ]
2	Permutations	Arrange all	[ ]
3	Combination Sum	Reuse allowed	[ ]
4	Combination Sum II	No reuse, skip dups	[ ]
5	Palindrome Partitioning	Partition + validate	[ ]
6	N-Queens	Row-by-row	[ ]
7	Word Search	Grid DFS	[ ]
8	Letter Combinations of Phone Number	Multi-branch	[ ]
9	Generate Parentheses	Open/Close counting	[ ]
10	Sudoku Solver	Cell-by-cell	[ ]