Combination Sum II
Medium · Backtracking · Array · Backtracking
Problem
You are given a list candidates, which may contain repeated values, and an integer target. Return every distinct combination of candidates whose values sum to target, where each element of the list can be used at most once.
Two combinations that use the same values the same number of times are the same combination and must be listed only once. The combinations may be returned in any order, and the values inside each one in any order.
Examples
Input: candidates = [3,1,3,5,1,1], target = 8 Output: [[1,1,1,5],[1,1,3,3],[3,5]]
Three combinations: [1,1,1,5], [1,1,3,3] and [3,5]. Using a different 1 or 3 does not make a new one.
Input: candidates = [4,2], target = 5 Output: []
Neither 4, 2, nor 4 + 2 equals 5.
Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
[1,1,6], [1,2,5], [1,7] and [2,6]. The two 1s can appear together because they are two separate elements.
Constraints
- 1 <= len(candidates) <= 100
- 1 <= candidates[i] <= 50
- 1 <= target <= 30
Approaches
- Baseline: take-or-leave every element, merge duplicates in a set — time O(2^n · n), space O(number of results · n)
Follow-up
If only the number of combinations is needed, the search can be replaced by counting: group equal values, and for each distinct value with c copies add the ways to use it 0..c times to every reachable sum. That table handles targets in the thousands, where listing would never finish.
Related problems
Start free on Cariara · Coding problems · System design studio
