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
(1) Java
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> rst = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return rst;
}
Arrays.sort(candidates);
Set<List<Integer>>[] dp = new Set[target+1];
for (int i = 0; i <= target; i++) {
dp[i] = new HashSet<List<Integer>>();
}
for (int j = 0; j < candidates.length; j++) {
int c = candidates[j];
for (int i = target; i >= 1; i--) {
if (c == i) {
List<Integer> l = new ArrayList<Integer>();
l.add(c);
dp[i].add(l);
} else if (c < i) {
Set<List<Integer>> l = dp[i-c];
for (List<Integer> ll : l) {
List<Integer> lll = new ArrayList<>(ll);
lll.add(c);
dp[i].add(lll);
}
}
}
}
for(List<Integer> l : dp[target]) {
rst.add(l);
}
return rst;
}
}
(2) Python
class Solution:
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
rst = []
if not candidates:
return rst
candidates.sort()
self.helper(candidates, target, rst, [], 0)
return rst
def helper(self, candidates, target, rst, path, start):
if target == 0:
path2 = list(path)
rst.append(path2)
return
elif target < 0:
return
for i in range(start, len(candidates)):
if i != start and candidates[i] == candidates[i-1]:
continue
path.append(candidates[i])
self.helper(candidates, target-candidates[i], rst, path, i+1)
path.pop()
(3) Scala