Backtracking Target: 15s
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)Type it from memory. Go.