Backtracking Core Idea

Backtracking is controlled brute force:

dfs(state):
    if state is complete:
        record answer
        return
 
    for choice in valid choices from state:
        choose
        dfs(next state)
        undo

Common Shapes

Pick Or Skip

Use when every element has exactly two choices: take it or leave it.

Examples: subsets, subset-sum brute force, partition equal subset sum baseline.

dfs(i):
    if i == n:
        add path
        return
 
    dfs(i + 1)              // skip nums[i]
 
    path.push(nums[i])      // pick nums[i]
    dfs(i + 1)
    path.pop()

This is the clearest way to learn subsets because the decision at each index is explicit.

Advance An Index With A Loop

Use when the recursion chooses the next item or cut from the remaining suffix.

Examples: subsets, combinations, combination sum, string partitioning.

dfs(start):
    if complete:
        add answer
        return
 
    for i = start; i < n; i++:
        choose i
        dfs(next_start)
        undo

This is the same idea as pick-skip for subsets, but the skipped elements are implicit: when the loop jumps from start to i, every earlier candidate in that loop was skipped. The loop version generalizes better to combinations, duplicate skipping, reuse, and string cuts.

Choose A Remaining Item

Use when order matters and each position can choose from unused values.

Examples: permutations, duplicate-aware permutations, tile sequences.

dfs():
    if path.size == n:
        add path
        return
 
    for choice in remaining choices:
        choose
        dfs()
        undo

Place Into A Constrained Position

Use when each row, cell, slot, or bucket has constraints.

Examples: N-Queens, Sudoku, matchsticks, k equal-sum subsets.

dfs(pos):
    if pos == total:
        add answer
        return
 
    for choice in choices:
        if safe(pos, choice):
            place
            dfs(pos + 1)
            remove

Pruning Rules

Sort first when it lets impossible branches break.
Skip duplicate choices at the same recursion depth.
Stop when a running sum exceeds the target.
Stop when remaining choices cannot fill the required size.
Cache suffix states when the recursion recomputes the same work.
Use constraint sets for O(1) safety checks.

Lest I Forget

Core Idea