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
| class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtrace(const vector<int>& candidates, int target,int start) {
if (target == 0) {
result.push_back(path);
return;
}
if (target < 0) {
return;
}
for (int i = start; i < candidates.size(); i++) {
path.push_back(candidates[i]);
target -= candidates[i];
backtrace(candidates, target,i);
path.pop_back();
target += candidates[i];
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtrace(candidates, target,0);
return result;
}
};
|
相较于之前的题目，数组中的元素同一个数字可以无限制重复被选取，我们就得保证当前元素在下一次选择中依旧可以选择自己。要记住这是一道组合题，后续的元素是不能往前看的，即不能再选择之前的元素。要想同时达到前面两个条件，我们的做法是 传递到 backtrace 中的 start 参数 不在 自加，既 传递 i 作为参数，而不是 i + 1 作为参数。
为什么组合中，其后的元素不能往前看，即不能再选择之前的元素？
因为我们的回溯会把当前元素和后面的元素所有可能都尝试一遍，而组合不强调顺序性，这就是为什么组合中其后的元素没有必要往前看。
