Hints — p37 Combinations

Hint 1. Same family as p36, but here {1,2} and {2,1} are the SAME thing. How do you avoid generating both?

Hint 2. Pick values in monotonically increasing order. Pass a start index — the next pick is from [start..n].

Hint 3. Skeleton:

def backtrack(start, path):
    if len(path) == k:
        result.append(path[:]); return
    for i in range(start, n + 1):
        path.append(i)
        backtrack(i + 1, path)   # i+1 — no reuse, monotonic
        path.pop()

Start the recursion with backtrack(1, []) (1-indexed!).

Hint 4. Pruning: if you still need need = k - len(path) more elements, the max i you can pick must leave need - 1 values above it. So i_max = n - need + 1. Loop upper bound: n - need + 2.

Hint 5. Variants:

• LC 39 (reuse): recurse with i, not i+1. Track target.
• LC 40 (dup input): sort + if i > start and a[i] == a[i-1]: continue.

If still stuck: see solution.py.