Backtracking

Every backtracking problem follows choose → explore → unchoose. The only things that change are the state, choices, and goal condition.

BACKTRACKING TEMPLATE
─────────────────────
def backtrack(state, choices):
    if is_goal(state):
        result.append(state[:])  # copy!
        return

    for choice in choices:
        if not is_valid(choice, state):
            continue

        # 1. CHOOSE
        state.append(choice)      # or modify state

        # 2. EXPLORE
        backtrack(state, next_choices)

        # 3. UNCHOOSE (undo mutation)
        state.pop()               # or restore state

CRITICAL POINTS:
  □ Copy state on goal (state[:] or list(state))
  □ Always undo mutations (symmetric choose/unchoose)
  □ Prune early with is_valid before recursing
  □ Track 'start index' for combinations to avoid dupes

DP counts/optimizes. Backtracking enumerates. If you need all solutions, backtracking. If you need the best/count, DP.

BACKTRACKING vs DP — DECISION GUIDE
────────────────────────────────────
USE BACKTRACKING when:
  □ Need ALL solutions (not just count/optimal)
  □ Solution is a sequence of choices (permutation, path)
  □ Constraints are complex (placement rules, validity)
  □ Search space can be pruned effectively
  Examples: N-Queens, Sudoku, all permutations

USE DP when:
  □ Need COUNT or OPTIMAL VALUE (not all solutions)
  □ Overlapping subproblems exist
  □ Optimal substructure holds
  □ State space is polynomial
  Examples: coin change, LCS, knapsack

BOTH work but pick wisely:
  "Number of ways to..." → usually DP (count)
  "Find all ways to..."  → usually backtracking (enumerate)
  "Min cost to..."       → usually DP (optimize)

HYBRID: precompute with DP, enumerate with backtracking
  Example: palindrome partitioning (DP palindrome check
           + backtracking to list all partitions)

Three core enumeration patterns. The only differences: does order matter, how many to pick, and the start index.

PERMUTATION vs COMBINATION vs SUBSET
─────────────────────────────────────
         ORDER     PICK ALL?   START IDX?
PERM     matters   yes (n)     no (use visited[])
COMBO    no        k items     yes (avoid revisit)
SUBSET   no        any count   yes (avoid revisit)

TEMPLATES:
  Permutations: for i in range(n):
                  if not used[i]: choose i
  Combinations: for i in range(start, n):
                  choose i, recurse with start=i+1
  Subsets:      for i in range(start, n):
                  choose i, record at every node

DUPLICATE HANDLING (sorted input):
  if i > start and nums[i] == nums[i-1]: continue

REUSE ALLOWED (combination sum):
  recurse with start=i instead of start=i+1

QUICK CHECK:
  "order matters?" → permutation → O(n!)
  "fixed size k?"  → combination → O(C(n,k))
  "all sizes?"     → subset → O(2^n)