解题：满足某种数字之和的所有数字形式[难度中] - 小组 - 伯乐在线
给出一组候选数字以及目标数字，结果返回所有配对情况。
[7]
[2, 2, 3]
列出本题过程： 2 2 2 2 �C 退出 2223 ，此时而且不需要进行后面的循环，这就是所谓的剪枝函数的。
2232 ― 后面不需要考虑 2 3 3 不行 后面不需要考虑，
从3开始，3 3 6 退出 3 6 不行，继续停止，直到 7 本身。
Read full article from 解题：满足某种数字之和的所有数字形式[难度中] - 小组 - 伯乐在线
给出一组候选数字以及目标数字，结果返回所有配对情况。
示例：
如：候选数字：2,3,6,7 and 目标和 7, 其中一组解为（可以重复出现）：[7]
[2, 2, 3]
思路：
那首先就是深搜，这道题前天刚做，现在拿出来继续；列出本题过程： 2 2 2 2 �C 退出 2223 ，此时而且不需要进行后面的循环，这就是所谓的剪枝函数的。
2232 ― 后面不需要考虑 2 3 3 不行 后面不需要考虑，
从3开始，3 3 6 退出 3 6 不行，继续停止，直到 7 本身。
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
|
class Solution {
public:
vector<int>temp;
vector<vector<int> >result;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
sumHelper(candidates,target,0,candidates.size());
return result;
}
void sumHelper(vector<int>& candidates,int target,int index,int length){
//index代表数组索引值，length代表数组长度
if(target==0){
//这里很巧的是，别人用sum求和，他不用，他是相减，只要等于0了，就会存入数组中。
result.push_back(temp);
return;//不需要返回
}
if(index>=length||target<0){//因为是求减法，如果不相等，立即返回||
//还有一种是索引值大于数组长度
return;
}
for(int i=index;i<=length-1;i++){
temp.push_back(candidates[i]);
sumHelper(candidates,target-candidates[i],i,length);
temp.pop_back();
}
}
};
|
