题目引入
题目:39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括
target）都是正整数。 - 解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
我的题解
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
combinationSumDFS(candidates, target, 0, {}, res);
return res;
}
void combinationSumDFS(vector<int>& candidates, int target, int start, vector<int> out, vector<vector<int>>& res) {
if (target < 0) return;
if (target == 0) {res.push_back(out); return;}
for (int i = start; i < candidates.size(); ++i) {
out.push_back(candidates[i]);
combinationSumDFS(candidates, target - candidates[i], i, out, res);
out.pop_back();
}
}
};
分析
如何想到递归
- 这道题明显和之前只要计算两数之和之类的题目不一样，我们要的得到的数字之和个数不限，对于这样的题目比较容易想到的就是递归
- 我们有一个目标target，在选择一个数后，会得到target - 选择数这样一个新的target，继续累加直到获得最后结果
递归函数分析
参数
- 递归函数(vector<int>& candidates, int target, int start, vector<int> out, vector<vector<int>>& res)这五个参数
- vector<int>& candidates：输入的数组
- target：目标数，在前一个数被选择出来后更新
- start：遍历时的开始下标
- out：一次结果数组
- res：最后输出的结果
出入口分析
- 出口：
- target < 0, 此时显然已经无法达成target，结束
- target = 0, 此时target已经达成，可以返回一个正确的out
- 入口
- 对于没有满足target的数，从start开始遍历（这里注意一点：start不是i + 1而是i，因为这道题允许重复使用元素，我们只要改变target）
- 遍历到的数先直接加入out，接着直接开始递归，结束后退出
类似题目
后记
- 类似题目中这道关键点是要学会去重，可以理解为，我们选择了一个数之后，在递归过程中，这个位置不希望出现一样的数，所以遍历时霸宠的的去掉
