Combination Problems in Backtracking

Three Flavours of Combination Problems

A combination is a group — order does not matter. Almost every combination problem is one of these three:

1. CHOOSE EXACTLY k OF n
   "Pick 2 of {1, 2, 3, 4}"
   → [1,2] [1,3] [1,4] [2,3] [2,4] [3,4]          C(4,2) = 6

2. REACH A TARGET, VALUES REUSABLE
   "Using coins of 2, 3, 5 (unlimited supply), make 8"
   → [2,2,2,2] [2,3,3] [3,5]

3. REACH A TARGET, EACH ITEM ONCE, ITEMS MAY REPEAT
   "Using the pieces [1, 4, 1, 3, 2], each at most once, make 5"
   → [1,1,3] [1,4] [2,3]

All three use the pick-next shape from the subsets page: a loop starting at start, so groups are never generated in more than one order. What changes is the index passed down, the stop rule, and the pruning.

Flavour 1: Choose Exactly k

choose(start, path):
    if len(path) == k:  record; return
    for j in start .. n-1:
        path.append(nums[j])
        choose(j + 1, path)        ← j+1: each element at most once
        path.pop()

Tree for k = 2, nums = [1, 2, 3, 4]:

                   []
        /       |       |      \
      [1]      [2]     [3]     [4]  ← dead end: nothing after 4
     / | \     / \      |
 [1,2][1,3][1,4][2,3][2,4][3,4]

Pruning: Not Enough Elements Left

[4] above is a wasted call — after 4 there is nothing left to complete the pair. In general, if the path still needs r = k − len(path) elements, the starting index j must leave at least r elements, so:

for j in start .. n - r:      ← instead of start .. n-1

k = 2, n = 4, path empty → r = 2 → j runs 0..2 → picks 1, 2, 3 only.
[4] is never created.

For C(20, 10) this cuts the number of calls by roughly half.
For small k on large n the saving is smaller but still free.

Flavour 2: Target Sum With Reuse

Now the group is complete when the running total equals the target, and a value can be picked again.

reach(start, remaining, path):
    if remaining == 0:  record; return
    for j in start .. n-1:
        if nums[j] > remaining: break        ← sorted input → stop early
        path.append(nums[j])
        reach(j, remaining - nums[j], path)  ← j, not j+1: reuse allowed
        path.pop()

Coins [2, 3, 5], target 8:

  [] 8
  ├── [2] 6
  │   ├── [2,2] 4
  │   │   ├── [2,2,2] 2
  │   │   │   └── [2,2,2,2] 0  ✓
  │   │   └── [2,2,3] 1         ✂ 3 > 1 ... break
  │   ├── [2,3] 3
  │   │   └── [2,3,3] 0         ✓
  │   └── [2,5] 1               ✂
  ├── [3] 5
  │   ├── [3,3] 2               ✂ 3 > 2
  │   └── [3,5] 0               ✓
  └── [5] 3                     ✂ 5 > 3

Passing j (not j + 1) allows [2, 2, 2, 2]. Starting the loop at start (not 0) prevents [3, 2, 3] from appearing as a separate answer — it is the same group as [2, 3, 3].

Flavour 3: Target Sum, Each Item Once, Repeated Values

Two items may carry the same value. Each item can be used once, but two groups that differ only by which copy of a value they used are the same answer.

pieces = [1, 4, 1, 3, 2], target 5

STEP 1: sort → [1, 1, 2, 3, 4]
STEP 2: pass j + 1 (each item once)
STEP 3: at each level, skip a value equal to the previous one:
            if j > start and nums[j] == nums[j-1]: continue
STEP 4: break as soon as nums[j] > remaining

  [] 5
  ├── [1] 4
  │   ├── [1,1] 3
  │   │   ├── [1,1,2] 1   ✂
  │   │   └── [1,1,3] 0   ✓
  │   ├── [1,2] 2         ✂ (3 > 2)
  │   ├── [1,3] 1         ✂
  │   └── [1,4] 0         ✓
  ├── ✂ second 1 at level 0 — same subtree as the first 1
  ├── [2] 3
  │   └── [2,3] 0         ✓
  ├── [3] 2               ✂
  └── [4] 1               ✂

  Answers: [1,1,3] [1,4] [2,3]

Code: All Three Flavours

Output:
choose 2 of 4 (6): [1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4]
calls with bound = 10
reuse, make 8 (3): [2, 2, 2, 2] [2, 3, 3] [3, 5]
once,  make 5 (3): [1, 1, 3] [1, 4] [2, 3]

With the "enough left" bound, choosing 2 of 4 takes 10 calls: the root, three single-element nodes ([1], [2], [3] — [4] is never created), and six complete pairs.

Side-by-Side Cheat Sheet

Combining Constraints

Real tasks often stack rules — for example "exactly k numbers, distinct, from 1 to 9, summing to s". Merge the pruning from each flavour:

pick(start, need, remaining):
    if need == 0:
        record if remaining == 0
        return
    for v in start .. 9:
        if v > remaining: break                ← sum bound
        if 9 - v + 1 < need: break             ← not enough values left
        pick(v + 1, need - 1, remaining - v)

Example: 3 distinct numbers from 1..9 summing to 9
  → [1,2,6] [1,3,5] [2,3,4]

Every extra rule is another chance to cut a branch early.

When Combinations Become DP

If the question asks how many groups reach a target — not to list them — the state (index, remaining) repeats across branches. A table of size n × target replaces the exponential search:

"List every way to make 8 from coins {2, 3, 5}"   → backtracking (output is the answer)
"Count the ways to make 1,000 from coins {...}"   → DP, O(n × target)
"Is there any subset of these 40 numbers = T?"    → DP or meet-in-the-middle

See the Knapsack Pattern page for the counting versions.

Common Mistakes

Looping from 0 instead of start. Every group appears once per ordering of its elements: [2, 3, 3], [3, 2, 3], [3, 3, 2].

Passing j + 1 when reuse is allowed (or j when it isn't). The first loses [2, 2, 2, 2]; the second lets one item be counted many times.

Using continue where break is valid. Correct, but slower — on sorted input every later candidate is also too large.

Allowing negative values with the break rule. The overshoot argument relies on all values being positive. With negatives or zeros, the running sum can come back down, so you cannot stop early (and zeros can create infinitely many groups when reuse is allowed).

Interview Questions

Q: How do you avoid generating the same combination in different orders?

Only ever pick elements at or after the index of the previous pick. Each group then has exactly one representation: its elements in input order. This is the start-index rule.

Q: What changes between "each item once" and "unlimited reuse"?

Only the index passed to the recursive call: j + 1 moves past the item just used, while j keeps it available. Everything else — the start-index loop, the target check, the sorted break — stays the same.

Q: Bound the running time of target-sum with reuse.

The depth is at most target / min_value, and each level branches up to n ways, so O(n^(target / min_value)) nodes in the worst case. Sorting plus the overshoot break prunes heavily in practice. If only the count is needed, DP solves it in O(n × target).

Summary

• ›Combinations are groups: use a start index so each group appears once.
• ›Choose k: recurse with j + 1, stop at size k, bound the loop at n − need.
• ›Target with reuse: recurse with j; sort and break on overshoot.
• ›Target, each once, repeated values: sort, recurse with j + 1, skip equal values at the same level.
• ›When only a count is needed, move to DP.

Next, N-Queens applies the same choose–explore–un-choose loop to a board, with O(1) attack checks that make the pruning nearly free.