← DSA Atlas
Dedicated problem page · #40

Combination Sum II

MediumBacktrackingSubset-sum backtracking with duplicate skippingDFS over a sorted array, each element used at most once
Solve on LeetCode ↗
40
MediumBacktrackingDFS over a sorted array, each element used at most onceSubset-sum backtracking with duplicate skipping

Combination Sum II

Given a collection of candidate numbers (which may contain duplicates) and a target, return all unique combinations that sum to target. Each number may be used at most once in a combination, and the result must not contain duplicate combinations.

Open official problem prompt ↗
In plain English

Enumerate every distinct multiset of the given numbers that adds up to the target, each occurrence usable once.

Picture it like this

Picking coins from a jar to make exact change, but each physical coin can be spent only once and you refuse to write down the same handful twice.

Example
Input
candidates = [10,1,2,7,6,1,5], target = 8
Output
[[1,1,6],[1,2,5],[1,7],[2,6]]
Why
Each listed multiset sums to 8, uses each chosen occurrence once, and no combination is repeated.
Constraints
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
Pattern lesson

See the pattern, then code

Subset-sum backtracking with duplicate skipping
Recognition clue

You need all combinations summing to a target from a multiset where each element is consumed once and duplicate combinations must be suppressed - sort then skip repeats at the same depth.

↗
Backtracking

Generate every valid combination, permutation, partition, or configuration.. Sorting groups equal values; within one recursion level, choosing the same value twice would regenerate an identical combination, so skip an element equal to its previous sibling. Advancing start to i+1 enforces single use.

New words, made simpleKnow these before the algorithm
Start index
The earliest position a branch may pick from, enforcing that elements are only used going forward.
Sibling duplicate
An equal value considered at the same recursion depth; skipping it prevents duplicate combinations.
Remaining target
Target minus the sum chosen so far; reaching 0 means success.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Generate all, dedupe with a set

Works but wastes time exploring duplicate branches and needs extra memory.

Backtrack ignoring duplicates, then store sorted tuples in a set to drop repeats.

Time O(2^n) plus hashing overheadSpace O(2^n) for the set
Best choiceSort + skip equal siblings + i+1

Prunes duplicate branches at the source with no post-processing.

Sort, advance start to i+1 for single use, and skip candidates[i]==candidates[i-1] when i>start.

Time O(2^n) with early breakSpace O(n)
The rule we keep true

Invariant

The path always holds a strictly-forward selection whose sum is target - remaining, and no two branches at the same depth start with the same value.

Why this is correct

Reasoning

Passing i+1 guarantees each array position is used at most once. Sorting makes equal values adjacent; skipping duplicates only at the same level (i>start) still lets a value repeat via distinct positions deeper in the path, so all genuine combinations appear exactly once.

The algorithm in three movesSay these aloud before coding
1Sort candidates so duplicates are adjacent and pruning is possible

sorted = [1,1,2,5,6,7,10]

2Recurse with a start index and the remaining target

path=[1], remain=7 -> pick next 1 (first at this level)

3When remaining hits 0, record a copy of the path

path=[1,1,6], remain=0 -> record

4At each level skip candidates[i] equal to candidates[i-1] (i > start) to avoid duplicate combinations

5Break early when candidates[i] exceeds remaining

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
11
22
53
64
75
106
1 · Read[10,1,2,7,6,1,5]
2 · Askarrange for pruning
3 · Update state[1,1,2,5,6,7,10]
4 · Resultrecursion begins at start=0, remain=8
Key takeaway

Sorted candidates; the highlighted 1,1,6 form one valid combination summing to 8.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 2-3Sort and init

    Sorting enables both duplicate skipping and the early break; res and path hold state.

  2. 2
    Lines 5-7Success base case

    remain == 0 means the current path sums to target, so append a copy.

  3. 3
    Lines 8-11Prune

    Skip equal siblings (i>start) to avoid duplicate combos; break once a candidate exceeds remain since the rest are larger.

  4. 4
    Lines 12-14Choose/explore/unchoose

    Recurse with i+1 for single use, then pop to restore the path.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • No combination sums to target -> return empty list
  • All candidates larger than target -> the early break yields nothing
  • Many duplicates of one value that combine with itself, e.g. [1,1,1,1] target 2
!

Common beginner mistakes

  • Using i instead of i+1, which allows reusing the same element (that is Combination Sum I)
  • Skipping duplicates with i>0 instead of i>start, which wrongly drops valid combinations that legitimately repeat a value
  • Forgetting to sort, breaking both the duplicate rule and the early break
Check your understanding

Why is the duplicate check i > start rather than i > 0?

More in Backtracking

#78SubsetsSubset enumeration by include/exclude#39Combination SumCombination search with unlimited reuse#46PermutationsPermutation generation#79Word SearchGrid path search with in-place visited marking#17Letter Combinations of a Phone NumberCartesian product of digit-letter groups#22Generate ParenthesesConstrained string construction