Given a collection of candidate numbers candidates and a target number target, find all unique combinations in candidates whose numbers add up to target.
Each number in candidates may be used at most once in a single combination. Note that candidates can contain duplicate values — so the same value may appear more than once in a combination, as long as it comes from different positions in the input.
The result must not contain duplicate combinations. Two combinations are considered the same when they use the same multiset of values, regardless of order — return each such handful only once.
candidates[i] == candidates[i-1] works, and it lets you prune the moment a value exceeds the remaining target.i to reuse the same number; here you recurse from i+1 because each position may be used at most once, plus you skip sibling duplicates from the input.i == start) must always be tried — skipping it would drop valid combinations. Only later duplicates at the same level are redundant.remaining == 0 instead of storing the combo — O(1) extra space beyond the recursion stack.i instead of i+1 and drop the sibling-duplicate skip (deduping input repeats up front instead).break on candidates[i] > remaining prunes whole subtrees for free — no separate bound check needed.Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [[1,1,6],[1,2,5],[1,7],[2,6]] There are two 1s in the input, so 1 + 1 + 6 is allowed. Each combination sums to 8 and uses each chosen position once.
Input: candidates = [2,5,2,1,2], target = 5 Output: [[1,2,2],[5]] 1 + 2 + 2 uses two of the three 2s; 5 stands alone. No handful is listed twice.
- 1 <= candidates.length <= 100 - 1 <= candidates[i] <= 50 - 1 <= target <= 30
Combination Sum II adds one twist to plain combination search: the input can repeat values, and you may use each position only once. That twist is exactly what a clean, sorted backtracking template is built to handle — this walkthrough takes you from a brute-force subset scan to that template.
In plain terms: choose a sub-collection of the given numbers (each index used at most once) that sums to target, and report the set of such sub-collections with duplicates removed. Formally, return all multisets S drawn from candidates (respecting multiplicity) with sum(S) == target, each listed exactly once.
Worked example — candidates = [10,1,2,7,6,1,5], target = 8
sort → [1,1,2,5,6,7,10] pick 1 → need 7 → pick 1 → need 6 → pick 6 ✓ [1,1,6] pick 1 → need 7 → pick 2 → need 5 → pick 5 ✓ [1,2,5] pick 1 → need 7 → pick 7 ✓ [1,7] pick 2 → need 6 → pick 6 ✓ [2,6] answer: [1,1,6], [1,2,5], [1,7], [2,6]
Naming the input guarantees before you code is what separates a senior candidate from someone who dives straight into a buggy recursion.
“Can candidates contain duplicate values?”
Yes is the whole difficulty — it forces us to skip repeats at each level instead of skipping numbers outright.
“Are all the numbers positive?”
Positive values let us abandon a branch the instant the running sum passes the target.
“If nothing sums to the target, what do we return?”
An empty list — a valid and common answer worth confirming up front.
“Does the order of numbers inside a combination matter?”
No — [1,2,5] and [5,2,1] are the same handful, so we fix one canonical (sorted) order.
“How large can candidates get?”
Up to 100 numbers, so a raw exponential subset scan is viable only with aggressive pruning.
Before I start, I have a couple of clarifying questions.
First — the array can contain duplicate values, and I may use each position at most once, correct?
And finally — if nothing adds up to the target, I will return an empty list; is that the expected output?
After sorting, identical numbers sit next to each other.
[1,1,2,5,6,7,10] ^ ^ the two 1s are now adjacent
So the vague rule "don't start two branches with the same value at the same step" becomes the concrete check "skip an element equal to the one directly on its left."
When we choose candidates[i], the next choice must start at i + 1, never i. That single shift enforces the use-once rule for every position, with no extra bookkeeping.
choose index i → recurse from i + 1
At one step, launching branches from two different positions that hold the same value produces identical sub-combinations twice. So skip candidates[i] when i > start and candidates[i] == candidates[i-1]. The i > start guard is key: it only blocks sibling repeats at the same level, so a value can still appear twice deeper in a branch when the input genuinely has two copies.
| Brute force | Sorted backtracking | |
|---|---|---|
| Idea | enumerate all 2^n subsets, dedupe with a set | grow a sorted combination, prune, skip sibling dups |
| Time | O(2^n · n) | O(2^n) worst case, far less after pruning |
| Space | O(2^n · n) for the set | O(n) recursion depth |
The full code for both lives in the Approaches selector below.
Key takeaway
Sort, then backtrack: advance the index to use each position once, and skip a value equal to its left neighbour at the same level to eliminate duplicate combinations at the source.
sort(candidates)
backtrack(start, remaining):
if remaining == 0: record combo; return
for i from start to n-1:
if i > start and candidates[i] == candidates[i-1]: continue
if candidates[i] > remaining: break # sorted: rest are larger
choose candidates[i]
backtrack(i + 1, remaining - candidates[i])
undo