非科班学习算法day23 | LeetCode39:组合总和 ，Leetcode40:组合总和||
介绍
包含LC的两道题目，还有相应概念的补充。
相关图解和更多版本：
代码随想录 (programmercarl.com)https://programmercarl.com/#%E6%9C%AC%E7%AB%99%E8%83%8C%E6%99%AF
一、LeetCode题目
1.LeetCode39:组合总和
题目解析
明确问题需求，组合：没有顺序要求，可以有重复；总和：中止条件，剪枝条件。
这里和之前题目最大的区别就是可以重复，也就是说可以从头开始，所以注意递归的参数是i
还有一个问题就是需不需要index，实际上是需要的，因为index可以帮助我们取寻找在一个数组中当前寻找元素的位置，比如说，一开始找的是0位，进入递归，下一层还是会从0开始选取；下一个for里面i已经++了，所以进入到1位的分支，以上这句话也可以增加对回溯的理解。
c++代码如下：
class Solution {
public:
// 路径
vector<int> path;
// 结果
vector<vector<int>> res;
// 回溯函数-重复选取
void backtracking(vector<int>& candidates, int target, int index, int sum) {
if (sum > target)
return;
// 中止,收集结果
if (sum == target) {
res.push_back(path);
return;
}
for (int i = index; i < candidates.size(); i++) {
path.push_back(candidates[i]);
sum += candidates[i];
backtracking(candidates, target, i, sum);
path.pop_back();
sum -= candidates[i];
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtracking(candidates, target, 0, 0);
return res;
}
};2.Leetcode40:组合总和||
题目链接：40. 组合总和 II - 力扣（LeetCode）
题目解析
这里有一个和前面不同的区别就是数组中有重复的数字，结果res里面的路径之间要求不可以相同，比如[1,1,1]没有问题，但是res里有两个[1,1,1]就不可以了。
明确了这个需求我们可以根据抽象的树状图分析出来，递归过程其实并没有影响，因为检索过程没有变，但是如果想去重就要把在树层上下功夫。这里没有采用used辅助，可以想象一下，什么能造成重复，前提是将数组排序，如果相邻两个数是一样的，因为我们for是从左到右遍历，那么后面的数构成的结果一定包含在前面的数里。
C++代码如下：
class Solution {
public:
// 路径
vector<int> path;
// 结果
vector<vector<int>> res;
// 回溯函数-有重复数字且同一位不可重复选取
void backtracking(vector<int>& candidates, int target, int sum, int index) {
if (sum > target)
return;
// 收集结果
if (sum == target) {
res.push_back(path);
return;
}
for (int i = index; i < candidates.size(); ++i) {
if (i > index && candidates[i] == candidates[i - 1])
continue;
path.push_back(candidates[i]);
sum += candidates[i];
backtracking(candidates, target, sum, i + 1);
path.pop_back();
sum -= candidates[i];
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, 0);
return res;
}
};注意点：其他地方都没有问题，只需要注意去重大多数是要重新排序的，除非说有序返回！
总结
打卡第23天，坚持！！！
