Backtracking

Canonical example: Letter Combinations of a Phone Number for digits = "23". Digit 2 maps to abc, digit 3 maps to def. We must output every string formed by picking one letter per digit, so backtracking is the natural fit (one decision per position, small branching factor).

digits = " 2    3 "
          |    |
          v    v
        a b c  d e f      <- choices per slot

map = { '2': "abc", '3': "def" }

State we carry:
  index  -> which digit we are deciding (0..len)
  path   -> letters chosen so far (a stack)
  result -> completed combinations

INITIAL:
  index  = 0
  path   = [ ]            (empty)
  result = [ ]            (empty)

The path is a mutable stack we push to before recursing and pop from after — that pop is the backtrack. index == len(digits) is the base case: a full combination is ready to record.

At index = 0 the digit is '2' → choices a,b,c. We pick the first, 'a': push it onto path and recurse to index = 1. This is safe because every letter of '2' is a legal first character, so no pruning is needed yet — we just commit and dive deeper.

index = 1   (just descended)

path stack (bottom -> top):
  +---+
  | a |   <- chose 'a' for digit '2'
  +---+

path as string: "a"

remaining digit to decide: '3' -> d e f
result = [ ]

We are now one level deep. The recursion will return here later so we can try 'b' and 'c' — that is the breadth at this level, explored one branch at a time.

At index = 1 the digit is '3' → choices d,e,f. Pick 'd', push it, recurse to index = 2. Now index == len("23") == 2: base case hit. The path is a complete combination, so we copy it into result. Copying (not aliasing) is safe and required, because path will keep mutating after we return.

index = 2  ==  len(digits)  -> BASE CASE

path stack:
  +---+
  | d |   <- top  (digit '3')
  +---+
  | a |   <- bottom (digit '2')
  +---+
path as string: "ad"   --copy-->  result

result = [ "ad" ]

No further choices exist past the last digit, so we stop descending and unwind back to index = 1 to try the siblings of 'd'.

Returning from the base case, we pop 'd' (un-choose) so path is just "a" again. The loop at index = 1 advances to 'e': push, recurse, hit base case, record "ae", pop. Then 'f': record "af", pop. The pop after each child is what keeps the stack clean for the next sibling — without it, letters would leak across branches.

back at index = 1, cycling choices d -> e -> f

after 'e':  path = [a][e] -> record "ae", then pop e
after 'f':  path = [a][f] -> record "af", then pop f

path stack now (all '3'-choices exhausted):
  +---+
  | a |   <- only the '2'-choice remains
  +---+

result = [ "ad", "ae", "af" ]

Digit '3' is fully explored under the prefix "a". We return to index = 0 to advance past 'a'.

The index = 1 call finishes, so we pop 'a' at index = 0, emptying path. The loop at index = 0 advances from 'a' to 'b': push 'b' and recurse into index = 1 again. The subtree under 'b' is explored with exactly the same machinery, producing "bd", "be", "bf".

back at index = 0, advanced 'a' -> 'b'

path stack:
  +---+
  | b |   <- fresh '2'-choice, 'a' was popped
  +---+
path as string: "b"

(recurse index=1 over d,e,f as before)

result = [ "ad", "ae", "af",
           "bd", "be", "bf" ]

Notice the stack never grows beyond len(digits) = 2 at any moment — backtracking gives us all 9 strings using O(depth) extra space, not O(number of results).

Pop 'b', advance to the last choice 'c' at index = 0, and recurse one final time over d,e,f. This adds "cd", "ce", "cf". After the 'c' subtree returns and 'c' is popped, the loop at index = 0 has no more letters — the recursion fully unwinds and path is empty again, matching its initial state.

index=0 choice 'c' -> recurse d,e,f

final path stack: (empty, all popped)
  +---+
  |   |
  +---+

result = [ "ad","ae","af",
           "bd","be","bf",
           "cd","ce","cf" ]   (3 x 3 = 9)

The empty final stack is the proof the algorithm is balanced: every push was matched by a pop, so no state leaked. That symmetry is the heart of correctness in backtracking.

Phone letters never prune (all choices are always legal), but the same skeleton scales to constrained problems by adding a validity check before recursing. The earlier you reject, the more of the tree you skip.

backtrack(index, path):
  if index == END:                # base case
      result.add(copy(path))
      return
  for choice in choices(index):
      if NOT valid(choice, path):  # <-- PRUNE here
          continue                 #     skip dead branch
      path.push(choice)            # choose
      backtrack(index+1, path)     # explore
      path.pop()                   # un-choose (backtrack)

Examples of valid():
  Permutations II : skip if choice used, OR
                    (choice == prev && prev not used)  // dedup
  Balanced parens : open
For Permutations II you sort first and skip a duplicate value whose identical predecessor is unused, killing duplicate subtrees. For Balanced Parentheses and Palindrome Partitioning the valid() guard rejects illegal prefixes immediately — same three-line choose/recurse/un-choose engine, different pruning rule. Master the symmetry and the guard, and all five lessons collapse into one pattern.