# 40. Combination Sum II
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]
# Solution
Approach 1: DFS.
# Code (Python)
Approach 1:
class Solution:
def combinationSum2(self, candidates, target):
candidates.sort()
result = []
#self._combinations(0, target, [], result, candidates) # OR
self._combinations2(0, target, [], result, candidates)
return result
def _combinations(self, start, target, current, result, candidates):
if target == 0:
result.append([_ for _ in current])
return
if target < 0 or start >= len(candidates):
return
current.append(candidates[start])
self._combinations(start + 1, target - candidates[start], current, result, candidates)
current.pop()
start = start + 1
# make sure start < len(candidates) to avoid out of boundary error
while start < len(candidates) and candidates[start] == candidates[start-1]:
start += 1
self._combinations(start, target, current, result, candidates)
def _combinations2(self, start, target, current, result, candidates):
if target == 0:
result.append([_ for _ in current])
return
if target < 0 or start >= len(candidates):
return
for i in range(start, len(candidates)):
if candidates[i] > target:
break # stop early
if candidates[i] == candidates[i-1] and i > start: # need i > start because for i == start we'll still take it
continue
current.append(candidates[i])
self._combinations(i + 1, target - candidates[i], current, result, candidates)
current.pop()
# Code (C++)
Approach 1:
class Solution {
private:
vector<vector<int>> solutionSet;
void combinationSum2(vector<int>& candidates, int head, int target, vector<int>& solution) {
if (target == 0)
{
solutionSet.push_back(solution);
return;
}
for (int i = head; i < candidates.size(); ++i)
{
if (i > head && candidates[i] == candidates[i-1])
continue;
if (candidates[i] > target)
break;
solution.push_back(candidates[i]);
combinationSum2(candidates, i + 1, target - candidates[i], solution);
solution.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> solution;
std::sort(candidates.begin(), candidates.end());
combinationSum2(candidates, 0, target, solution);
return solutionSet;
}
};