当C++遇上LeetCode——递归求组合

题目引入

题目: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，接着直接开始递归，结束后退出

类似题目

• 40.组合求和II

后记

• 类似题目中这道关键点是要学会去重，可以理解为，我们选择了一个数之后，在递归过程中，这个位置不希望出现一样的数，所以遍历时霸宠的的去掉