[数据结构与算法]递归总结（含有题目）

目录

递归一般思路：

1.找到边界，是i==n还是i==n+1？

2.答案的获取，下面的两道题一般都是使用变长数组套变长数组的形式。

3.递归的对称，用了一个递归，放进去了一个数，如果下一次也要用，那很好，没问题，但是如果下一次不用，那一定会出现问题，就需要拿出来，做出各种细节的处理！

题目：

1.子集

2.组合

递归一般思路：

递归分为三个部分：

1.找到边界，是i==n还是i==n+1？

2.答案的获取，下面的两道题一般都是使用变长数组套变长数组的形式。

3.递归的对称，用了一个递归，放进去了一个数，如果下一次也要用，那很好，没问题，但是如果下一次不用，那一定会出现问题，就需要拿出来，做出各种细节的处理！

题目：

1.子集

给你一个整数数组?nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：

输入：nums = [0]
输出：[[],[0]]
?

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets
?

思路：
可以类似看成一棵树，从上到下不断递归，两边的偏向分为--要这个数/不要这个数

?所以一共运行2 的n次方，最左边一个数都没有，最右边有所有的数。

左边用完了之后，要对称搞掉，如果存着会造成重复。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        n = nums.size();
        recur(nums,0);
        return ans;
    }

private:
    void recur(vector<int>& nums,int i){  
        //首先定义边界情况
        if(i == n){
            //得到ans的值
            ans.push_back(chosen);
            return; 
        }
        recur(nums,i+1);
        chosen.push_back(nums[i]);
        recur(nums,i+1);
        chosen.pop_back();
    }
    int n;
    vector<int> chosen;
    vector<vector<int>> ans;
};

2.组合

给你一个整数数组?nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：

输入：nums = [0]
输出：[[],[0]]
?

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets

思路：

和前面的子集那道题大同小异，主要是要判断是否为k。

如果直接在if里面让你想等求解，会让运行速度慢很多很多，

所以这里就会有个角度--剪枝，如果chosen的已经比k大了，很好，你可以滚蛋了，如果chosen加上所有的都比那个小，那不行，你也要滚蛋！
?

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        this->n=n;
        this->k=k;
        recur(1);
        return ans;
    }


private:
    void recur(int i){  
        //首先定义边界情况
        if(chosen.size()>k||chosen.size()+n-i+1<k) return;
        if(i == n + 1){
            //得到ans的值
            ans.push_back(chosen);
            return; 
        }
        recur(i+1);
        chosen.push_back(i);
        recur(i+1);
        chosen.pop_back();
    }
    vector<int> chosen;
    vector<vector<int>> ans;
    // int j=1;
    int n;
    int k;
};