-
Notifications
You must be signed in to change notification settings - Fork 2
/
40. Combination Sum II.cpp
38 lines (37 loc) · 1.52 KB
/
40. Combination Sum II.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
vector<vector<int>> res;
vector<int>temp;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
if(candidates.empty()) return res;
sort(candidates.begin(),candidates.end());
helper(0,candidates, target);
return res;
}
void helper(int start, vector<int>& candidates, int target){
if(target==0){
res.push_back(temp);
return;
}
if(start>=candidates.size() ||target<0) return;
for(int i=start;i<candidates.size();i++){
if(i>start && candidates[i]==candidates[i-1]) continue;
temp.push_back(candidates[i]);
helper(i+1,candidates, target-candidates[i]);
temp.pop_back();
}
}
};
//第二种方法也很容易理解,1 1 1,再加一个和之前相同的数字,抛弃
//一次通过 一次AC,与第一题还是有不同的地方
//target==0) 这个条件要放在前面
// 要及时的存进去,这边如果调换位置,那么[1]1就会返回为空啊
/*if(target==0){
res.push_back(tem);
return;
}
if(target<0)
return; */
//还是在回溯那边,有关位置顺序的地方出错啊,以后记住,谁在前面,先考虑谁啊 还行啊
// 第一种方法更容易理解,其实这个时候还是要练习一下前面那题哦 https://leetcode.com/problems/permutations-ii/
// target<0 这块总是记不住啊,及时生活对我不公,还是要忍受啊