Combination Sum II

The key idea

Sort first, then DFS. Each number may be used once, so the recursion advances the start index past the number it just picked. To avoid duplicate combinations, skip any candidate equal to its left neighbor *at the same depth* — that sibling would only re-explore a branch already covered.

Problem

Given a collection of candidate numbers candidates (which may contain duplicates) and a target number target, find all unique combinations in candidates where the chosen numbers sum to target.

Each number in candidates may be used at most once in a combination.

The solution set must not contain duplicate combinations. Two combinations are the same if they contain the same multiset of numbers regardless of order.

Constraints

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

Examples

Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [[1,1,6],[1,2,5],[1,7],[2,6]]

Input: candidates = [2,5,2,1,2], target = 5 Output: [[1,2,2],[5]]

Complexity

Time: O(2^n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →