Combinations & combination sum
In one line
Combination problems pick unordered groups that meet a rule such as size k or a target sum; the start index prevents reordered duplicates, and a running remainder lets you stop early.
What it is
A combination is an unordered selection, like a subset with an extra rule. The common interview versions are: choose k numbers from 1..n, and combination sum, where you pick numbers that add up to a target.
The variants differ in two switches. Can a number be reused? If yes, recurse with the same index i; if no, recurse with i + 1. Does the input contain duplicates? If yes, sort and skip equal values at the same level.
Combination Sum (reuse allowed, distinct candidates), Combination Sum II (each candidate once, may contain duplicates) and Combination Sum III (k numbers from 1 to 9 summing to n) are all the same template with these switches set differently.
Why interviewers ask
This is one of the most asked backtracking families because small changes in the statement change the code. Interviewers watch whether you choose i vs i + 1 correctly, deduplicate properly, and prune with sorting instead of exploring dead branches.
How it works
- 1Sort the candidates so you can stop the loop as soon as one is larger than what remains.
- 2State: path and remaining (target minus the sum of path).
- 3Goal: remaining == 0, record a copy. If remaining would go negative, that branch is dead.
- 4Loop i from start: if candidates[i] > remaining, break, because every later candidate is even larger.
- 5Choose candidates[i], recurse with start = i (reuse allowed) or i + 1 (use once), then pop.
- 6With duplicate candidates and use-once, also skip i when i > start and candidates[i] == candidates[i - 1].
Worked example · combination_sum([2, 3, 6, 7], target = 7)
- Root, remaining 7: pick 2 -> remaining 5.
- Pick 2 again -> 3. Pick 2 again -> 1: now 2 > 1, so break. Back at remaining 3, try 3 -> 0: record [2, 2, 3]. Next is 6 > 3, break.
- Back at remaining 5 (path [2]), try 3 -> 2: 3 > 2, break. Try 6 > 5, break.
- Back at the root, try 3 -> 4: try 3 -> 1, break; 6 > 4, break. Try 6 -> 1: 6 > 1, break.
- Try 7 -> 0: record [7].
- Result: [[2, 2, 3], [7]]. [3, 2, 2] is never produced because we only move forward from start.
Picture it
Paying exactly 7 coins' worth with coins of 2, 3, 6 and 7. You sort the coins, always add coins in non-decreasing order so you never count 2+2+3 and 3+2+2 separately, and stop trying bigger coins as soon as one is more than you still owe.
Reference code
def combination_sum(candidates, target):
candidates = sorted(candidates)
result, path = [], []
def backtrack(start, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
c = candidates[i]
if c > remaining:
break # sorted: every later c is too big
path.append(c)
backtrack(i, remaining - c) # i, not i + 1: c may be reused
path.pop()
backtrack(0, target)
return result
print(combination_sum([2, 3, 6, 7], 7)) # [[2, 2, 3], [7]]Recursing with i (not i + 1) lets a candidate repeat, while never going back to earlier indices keeps each combination in non-decreasing order, so it appears once. Sorting enables the break, which prunes whole groups of branches. This works because all candidates are positive.
Key patterns
Reuse allowed (unbounded)
When: Combination Sum I, coin-change style listing
How: Recurse with start = i so the same candidate can be picked again.
Use once with duplicates
When: Combination Sum II
How: Sort, recurse with i + 1, skip if i > start and nums[i] == nums[i - 1].
Fixed size k
When: Choose k from n, Combination Sum III
How: Stop when len(path) == k; also prune if not enough numbers remain to reach k.
Sorted early break
When: Any target-sum search with positive numbers
How: Sort ascending and break the loop when a candidate exceeds the remainder.
Real-world use
Lineup and team selection tools
Fantasy sports lineup optimisers pick a fixed number of players per position under a salary cap; small pools are searched with combination backtracking and bound pruning, larger ones with integer programming.
Gift cards and vouchers
Checkout systems that combine a few gift cards or vouchers to match an order total exactly face a combination-sum problem; with only a handful of cards, exhaustive search is instant.
Combinatorial test design
Test planning tools choose k-way combinations of parameters to cover; listing combinations of k parameters out of n is the 'choose k from n' template.
In a project
An accounting tool must find which unpaid invoices (up to 25 per customer) add up exactly to a bank transfer the customer sent without a reference.
- Treat invoice amounts in cents as candidates, each usable once, and the transfer amount as the target.
- Sort amounts descending so large invoices are tried first and the remaining amount shrinks fast.
- Prune when an amount exceeds the remainder, and when the sum of all remaining invoices is less than the remainder.
- Return all exact matches; if there is more than one, show them to an accountant to choose.
Impact: Accountants stop matching transfers by hand. Most cases resolve in milliseconds, and ambiguous cases are flagged instead of guessed, which avoids posting payments to the wrong invoices.
Trade-offs
Use it when
- You must list every combination meeting the rule
- Candidates are few and positive, so the remainder shrinks quickly
- The rule is easy to check on a partial combination
Avoid it when
- Only the number of combinations or a yes/no answer is needed: coin change or subset sum DP is O(n * target)
- Candidates can be zero or negative: the remainder no longer shrinks and the search may not end
- The target is huge and candidates are tiny: the tree becomes extremely deep
Cost: Exponential. For combination sum a common bound is O(N^(T/M + 1)), where N is the number of candidates, T the target and M the smallest candidate. Choosing k of n produces n choose k results at O(k) each. Extra space is O(T/M) recursion depth.
Common mistakes
- Mixing up i and i + 1, which either forbids reuse when it is allowed or creates infinite recursion with a zero candidate.
- Restarting the loop at 0, which produces [2, 3, 2] and [3, 2, 2] as separate answers.
- Using continue instead of break after sorting, which still works but wastes the pruning.
- Deduplicating Combination Sum II with a set of results instead of the same-level skip.
- Forgetting that the approach assumes positive numbers.
Interview questions
Quick revision
- Reuse allowed: recurse(i). Use once: recurse(i + 1).
- Never loop from 0 for combinations: that makes orderings.
- Sort + break when candidate > remaining.
- Duplicates in input: skip if i > start and nums[i] == nums[i - 1].
- Choose k of n: record when len(path) == k; n choose k results.
- Counting only? Use DP instead of listing.
- Assumes positive candidates.
Check yourself
1. In Combination Sum I (each candidate may be reused), what start index does the recursive call use?
2. What does combination_sum([2, 3, 5], 8) return?
3. Why sort the candidates first?
4. Why does looping from start (not from 0) avoid duplicate combinations?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.