You are given an array candidates (which may contain repeated numbers) and an integer target. Return every unique combination of candidates whose sum equals target. Each element of the array may be used at most once, and the answer must not contain the same combination twice. Combinations may be returned in any order.
[1,1,6], but [1,7] appears only once even though there are two 1s.- 1 <= candidates.length <= 100
- 1 <= candidates[i] <= 50
- 1 <= target <= 30
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force generates all 2^n subsets, keeps those with the right sum and removes duplicates with a set, which is slow and wasteful. After sorting, equal numbers sit together. At any single level of the recursion, picking the first 1 or the second 1 as "the next number" leads to exactly the same combinations, so we only try the first copy at that level. Deeper levels can still use the second copy, which is how [1,1,6] is still found. Sorting also lets us break the loop as soon as a candidate exceeds the remaining target.
Algorithm
- Sort
candidates. - Define
backtrack(start, remain, path). Ifremain == 0, record a copy ofpath. - Loop
ifromstart. Ifi > startandnums[i] == nums[i-1], skip it (duplicate at this level). - If
nums[i] > remain, break: every later number is even bigger. - Add
nums[i]topath, recurse withstart = i + 1andremain - nums[i], then remove it.
O(2^n * n) in the worst caseSpace: O(n) recursion depth, excluding the outputi > start, not i > 0. Using i > 0 also blocks the second copy at a deeper level and loses answers like [1,1,6].class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: nums = sorted(candidates) res, path = [], []Β def backtrack(start, remain): if remain == 0: res.append(path[:]) return for i in range(start, len(nums)): if i > start and nums[i] == nums[i - 1]: continue # same value already tried at this level if nums[i] > remain: break # sorted, so the rest are too big path.append(nums[i]) backtrack(i + 1, remain - nums[i]) path.pop()Β backtrack(0, target) return res