Backtracking and constraint search · HTML
dfs(start,path) chooses a next index i in [start,n). Single-use combinations recurse to i+1; reusable candidates recurse to i. Emit a snapshot when target depth or condition is met.
Recognition signals
- All subsets, k-combinations, or constraint-satisfying selections must be listed.
- Element order does not distinguish results.
- Each candidate is usable once, a bounded number of times, or repeatedly.
- Pruning is useful but concrete witnesses are still required.
- n is small and output itself may be exponential.
False friends
| Signal | Why it is different |
|---|
| Only a count or feasibility bit | DP or a combinatorial formula can avoid output-level search when the target dimension is manageable. |
| Different orders are distinct answers | That is permutation or ordered construction; start would erase valid outcomes. |
| Unconstrained full subset iteration | Bitmask enumeration may be simpler when no structured pruning is needed. |
Core invariant
On entering dfs(start), path indices are strictly increasing and already fixed below start. The call generates exactly completions whose next index is at least start, preventing duplicate orders.
State, transition, and processing order
| Item | Definition |
|---|
| State | Next candidate index start, current path, remaining slots/target, and incrementally maintained constraints such as sum. |
| Transition | Choose i, update path and constraints, recurse to i+1 or i, then undo exactly that choice. |
| Frontier / order | The current path in an implicit decision tree; the loop explores next choices horizontally and recursion deepens vertically. |
Python skeleton
def combinations(nums, k):
out, path = [], []
def dfs(start):
if len(path) == k:
out.append(path.copy())
return
need = k - len(path)
last_start = len(nums) - need
for i in range(start, last_start + 1):
path.append(nums[i])
dfs(i + 1)
path.pop()
dfs(0)
return out
Correctness sketch
- Every emitted path has increasing indices, so each index is used at most once in canonical order.
- Every k-set has one increasing index sequence, and the loops can follow that sequence to a base case, proving completeness.
- Because the canonical sequence is unique, two recursion paths cannot emit the same indexed combination.
Complexity
| Time | Space | Parameters |
|---|
| Θ(C(n,k)·k) for k-combinations; Θ(n·2^n) for materialized subsets | O(k) stack/path excluding output | n is candidates and k selections; output size is an unavoidable lower bound. |
Edge cases
- k=0
- k>n
- duplicate input values
- candidate reuse policy
- copying the emitted path
- remaining-candidate pruning
Error patterns
| Pattern | Why it fails / fix |
|---|
| Restarting each recursion at zero | The same set appears in many orders and an index may be reused. |
| Appending path without a copy | Every result aliases one mutable list and changes together. |
| Forgetting to pop after recursion | Sibling branches inherit stale state; choose and undo must be mirror operations. |
| Assuming start removes duplicate values | It removes index-order duplicates, not equal values at distinct indices; sort and skip same-level duplicates. |
Selection and exclusion rules
- Decide whether order distinguishes answers.
- Specify candidate reuse to choose i+1 versus i.
- Accept output-scale complexity only when witnesses are required.
- Use only pruning conditions that prove completion impossible.
Original micro-example
| Part | Detail |
|---|
| Result | Blue-red never reappears because its index order is noncanonical. |
| Setup | Choose two colors from [red, blue, green]. |
| Trace | Increasing indices generate red-blue, red-green, and blue-green. |
Recall prompts
My notes