组合总和 2 中等🌟🌟🌟
问题描述
原文链接：40. 组合总和 II
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次 。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
提示:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
代码实现
Java
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
backTrack(candidates, target, 0, 0);
return res;
}
/*
怎么处理重复的组合
1. 排序 [1, 1,5, 6,7,10];
*/
void backTrack(int[] candidates, int target, int index, int sum){
if(sum > target){
return;
}
// 结束条件
if(sum == target){
res.add(new ArrayList<>(temp));
return;
}
// 处理主要逻辑
for(int i = index; i < candidates.length; i++){
// 去除重复的组合
if(i > index && candidates[i] == candidates[i-1]){
continue;
}
// 从多个元素选择一个
temp.add(candidates[i]);
sum = sum + candidates[i];
backTrack(candidates, target, i + 1, sum);
// 撤销之前的操作
temp.remove(temp.size() - 1);
sum = sum - candidates[i];
}
}
}
Python
class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = []
temp = []
candidates.sort()
self.backTrack(candidates, target, 0, 0, temp, res)
return res
def backTrack(self, candidates, target, index, sum, temp, res):
# 结束条件
if sum > target:
return
if sum == target:
# 结束条件
res.append(list(temp))
return
for i in range(index, len(candidates)):
# 去除重复的组合
if i > index and candidates[i] == candidates[i - 1]:
continue
# 从多个元素选择一个
temp.append(candidates[i])
sum += candidates[i]
self.backTrack(candidates, target, i + 1, sum, temp, res)
# 撤销之前的操作
temp.pop()
sum -= candidates[i]
C++
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> temp;
sort(candidates.begin(), candidates.end());
backTrack(candidates, target, 0, 0, temp, res);
return res;
}
void backTrack(vector<int>& candidates, int target, int index, int sum, vector<int>& temp, vector<vector<int>>& res) {
// 结束条件
if (sum > target) {
return;
}
if (sum == target) {
// 结束条件
res.push_back(temp);
return;
}
for (int i = index; i < candidates.size(); i++) {
// 去除重复的组合
if (i > index && candidates[i] == candidates[i - 1]) {
continue;
}
// 从多个元素选择一个
temp.push_back(candidates[i]);
sum += candidates[i];
backTrack(candidates, target, i + 1, sum, temp, res);
// 撤销之前的操作
temp.pop_back();
sum -= candidates[i];
}
}
};
Go
func combinationSum2(candidates []int, target int) [][]int {
res := [][]int{}
temp := []int{}
sort.Ints(candidates)
backTrack(candidates, target, 0, 0, &temp, &res)
return res
}
func backTrack(candidates []int, target, index, sum int, temp *[]int, res *[][]int) {
// 结束条件
if sum > target {
return
}
if sum == target {
// 结束条件
copyTemp := make([]int, len(*temp))
copy(copyTemp, *temp)
*res = append(*res, copyTemp)
return
}
for i := index; i < len(candidates); i++ {
// 去除重复的组合
if i > index && candidates[i] == candidates[i-1] {
continue
}
// 从多个元素选择一个
*temp = append(*temp, candidates[i])
sum += candidates[i]
backTrack(candidates, target, i+1, sum, temp, res)
// 撤销之前的操作
*temp = (*temp)[:len(*temp)-1]
sum -= candidates[i]
}
}