leetExpert

Module 16 · Recursion & Backtracking

Practice

Practice~2 min

How to practice this module

Backtracking drills reward the choose-explore-unchoose rhythm: record at a complete state, prune early, and always undo. Subsets and permutations are the pure tree; combination-sum and parentheses add constraints; palindrome-partitioning and n-queens prune harder. Done when all six show Solved in the hub.

Problems

Recursion — work them in order; difficulty ascends.

0/6

solved

  1. 1SubsetsMediumInclude / exclude treeWatch for: Branch on taking or skipping each element and advance the index; hand each answer a copied list, never a shared one
  2. 2PermutationsMediumSwap-based treeWatch for: Swap, recurse, swap back; a used-index approach must track exactly which positions remain
  3. 3Combination SumMediumUnbounded choice treeWatch for: The same candidate may repeat — recurse on the same index after taking; sorting candidates makes the prune sound
  4. 4Generate ParenthesesMediumCount-constrained branchingWatch for: Only add ')' when open > close; the two counters prune the tree — never validate the full string afterwards
  5. 5Palindrome PartitioningMediumPrefix-split treeWatch for: Cut a valid palindrome prefix and recurse on the remainder; reject the branch when the prefix itself is not a palindrome
  6. 6N-QueensHardPlace + prune boardWatch for: Check columns and both diagonals before placing; index arrays by column and diagonal to keep the check O(1)

Cheatsheet

Recursion — Choose → explore → unchoose. The call stack is your state.

Smell → pattern

  • All subsets / permutationsBacktracking tree
  • Constraint board (N-Queens…)Place + prune
  • Divide structure in halfRecurse on parts
  • Every valid arrangement / pathEnumerate + record

Patterns

Backtracking template

Core

Smell: Enumerate valid configurations

Push a choice, recurse, pop. Record when a complete valid state is reached. Prune early when constraints break.

return

Include / exclude

Safe

Smell: Subsets / combination sum

For subsets: branch on taking nums[i] or not, then advance i. Same tree, two edges.

return

Swap permutations

Reach

Smell: All orderings of a sequence

For i…n, swap i with j≥i, recurse i+1, swap back. Generates each order once.

write region

Place + prune (constraints)

Careful

Smell: N-Queens, Sudoku, safe placement

Check constraints before recursing, not after recording. Pruning at the placement step is what keeps board searches from degenerating into full enumeration.

return

Complexity targets

  • Subsets

    Time
    O(2ⁿ · n)
    Space
    O(n)
    Note
    Output-sensitive

  • Permutations

    Time
    O(n! · n)
    Space
    O(n)
    Note
    Depth-n stack

Traps

  • Mutating shared arrays

    Push a copy into the answer (or copy on record). Otherwise every result points at the same final list.

  • Forgetting to unchoose

    After recurse, undo the mutation (pop, unmark, swap back). Missing undo corrupts every sibling branch.

  • Pruning after the record

    If you record partial answers and only reject them later, you still walk the dead branches. Reject at the choice, not at the leaf.