题目描述
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例：
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
题目链接： https://leetcode-cn.com/problems/combination-sum-ii/
做这题之前可以先做一下组合总和。
思路
使用回溯。这个题的思路总体和组合总和的思路是一样的，这道题多了限制条件，第一个是每个数字只能用一次，所以递归的其实位置要是当前位置的下一个位置；另一个问题是数组中有重复的数字，这样最终的结果中也会有重复的答案，所以要去重。去重的方法是对数组进行排序，然后找和起始位置不同的数字开始递归，类似于全排列II。具体代码如下：
class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
if(candidates.empty() || target<=0) return {{}};
vector<int> track;
int curSum = 0;
int start = 0;
sort(candidates.begin(), candidates.end()); // 对数组排序
dfs(candidates, start, curSum, target, track);
return ans;
}
void dfs(vector<int> candidates, int start, int curSum, int target, vector<int> track){
if(curSum==target){
ans.push_back(track);
return;
}
if(curSum>target) return;
for(int i=start; i<candidates.size(); i++){
if(candidates[i]>target) continue; // 当前数字大于target,因为数组升序,所以不可能组合得到target
if(i>start && candidates[i]==candidates[i-1]) continue; // 去重
curSum += candidates[i];
track.push_back(candidates[i]);
dfs(candidates, i+1, curSum, target, track);
curSum -= candidates[i];
track.pop_back();
}
}
};
总结
一般题目中要求“答案中不能包含重复的数字”，通常的做法是对数组进行排序，然后在添加元素到答案中时添加一些条件。