The problem
Given an array candidates, which may contain repeated values, and a target, return every different combination that adds up to target. Each element may be used at most once. Any order, no repeated combinations.
Examples
01
- Input
candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
- Output
[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
02
- Input
candidates = [2, 5, 2, 1, 2], target = 5
- Output
[[1, 2, 2], [5]]
Constraints
- 1 ≤ candidates.length ≤ 100
- 1 ≤ candidates[i] ≤ 50
- 1 ≤ target ≤ 30
The idea
This is Combination Sum with two changes. Each element is used at most once, so after choosing candidates[i] the next choice starts at i + 1.
And repeats in the input would produce repeated combinations, so do as in Subsets II: sort, and among the options for one spot, skip a value equal to the one just tried. Sorting also means that once a value is too big, all the rest are.
- Time
- O(n · 2ⁿ) in the worst case
- Space
- O(n) besides the answer
Solution · every language run against every case
class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() # equal values side by side, and too big means every later one is too out, cur = [], [] def pick(start, left): if left == 0: out.append(cur[:]) return for i in range(start, len(candidates)): if i > start and candidates[i] == candidates[i - 1]: continue # the same value in the same place would repeat a combination if candidates[i] > left: break cur.append(candidates[i]) pick(i + 1, left - candidates[i]) # each candidate used at most once cur.pop() pick(0, target) return out