一.内容介绍

递归

https://www.zhihu.com/question/31412436/answer/683820765
对于递归，先考虑递归的边界条件，也即一般情况外的特殊情况，可以直接返回给调用函数的。
递归的栈点在函数再次被调用的地方，因此在写后面的递归式时，将特殊情况稍微一般化（比如从特殊情况下的只有一个结点，增加到两个结点），也即怎么从一般情况过渡到特殊情况，将问题进一步简化

递归有两种搜集数值的方式，一种是向下递深时，以传引用的方式，一种是向上归时，将需要的值作为函数返回值给返回回去。

回溯算法-（解决组合问题）

  1. 递归+循环，最经典的是组合问题，在每一层决定是否将该层的对象加入到组合中，并继续往下递归。
  2. 可以进行适当地剪枝操作（增加判断）来减少不必要的递归。
  3. 采用传引用的方式，来帮助存储最后满足条件的组合。
  4. 对于组合问题，如果组合的数互不相同（只考虑当前对象加入与否），则只需要递归就行了，但是若nums里有重复的数，则就需要在递归的该层上，进行一次循环，来把重复的一并进行考虑，防止重复（见90题.子集||）

二. 相关题目

40.组合总和||-(回溯算法)

题目链接

  1. 出发点是递归法，在递归的每一层决定该层所在的位置的数是加入还是不加入，并继续往下递归。但是这种方法不能解决重复问题，并且会超时。
  2. 更进一步，先对candidates进行排序，把相同的数放在同一层递归里考虑，用循环，也即该数出现0次，出现1次，出现2次…… ```cpp void Helper(int sum, int cur,int target,vector candidates,vector chosen, vector> & res) {
    1.  if (sum==target) {
    2.      res.push_back(chosen);
    3.      return;
    4.  }
    5.  if (sum>target||cur>=candidates.size())
    6.      return;
    7.  int i;
    8.  for (i=cur;i<candidates.size()-1&&candidates[i]==candidates[i+1];i++);
    9.  for (int j=0;j<=(i-cur+1);j++) {
    10.      Helper(sum+j*candidates[cur],i+1,target,candidates,chosen,res);
    11.      chosen.push_back(candidates[cur]);
    12.  }
    13.  return;
    } vector> combinationSum2(vector& candidates, int target) {
     sort(candidates.begin(),candidates.end());
 vector<vector<int>> res;
 vector<int> chosen;
 Helper(0,0,target,candidates,chosen,res);
 return res;

}

<a name="T6iIv"></a>
## 46.全排列-(回溯算法)
[题目链接](https://leetcode-cn.com/problems/permutations/)

1. 此处的递归为问题规模n的递归，当n=1时，一种，当n>1时，比如数组[1,2,3]，可以变成1+[2,3]，2+[1,3]，3+[2,1]，这样问题规模缩小为2，然后是[2,3]可以拆分成2+[3]，就唯一确定了这个排列，存储下来即可，其余类似。
1. 递归+循环，总是交换当前规模下的首位数字和剩余数字的位置，相当于确定下来首位数字，然后将剩下的未确定数字进行递归。因此需要start变量来标识数组中剩下是数字的开始位置，也是较小规模问题的起始位置。
```cpp
void Helper(vector<int> nums,int start,vector<vector<int>> & res) {
        int i,j,temp;
        if (start==nums.size()-1){
            res.push_back(nums);
            return;
        }
        for (i=start;i<nums.size();i++) {
            temp=nums[i];
            nums[i]=nums[start];
            nums[start]=temp;
            Helper(nums,start+1,res);
            temp=nums[i];
            nums[i]=nums[start];
            nums[start]=temp;

        }
        return;
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        Helper(nums,0,res);
        return res;

    }

47.全排列||

题目链接

  1. 对于全排列的递归，不一定需要用start的方式，也可以用visited[]的方式，使用过则标为1，并且用一个空数组来将被选择的数进栈，保证原数组不变化。

90.子集||

题目链接

  1. 典型的递归与回溯之间的区别
    void Helper(vector<vector<int>>& res,vector<int> nums,vector<int> ans,int cur) {
     if (cur==nums.size()){
         res.emplace_back(ans);
         return;
     }
     int i,count=1;
     for (i=cur+1;i<nums.size()&&nums[i]==nums[cur];i++,count++);
     for (i=0;i<=count;i++) {
         Helper(res,nums,ans,cur+count);
         ans.emplace_back(nums[cur]);
     }
     return;
 }
 vector<vector<int>> subsetsWithDup(vector<int>& nums) {
     sort(nums.begin(),nums.end());
     vector<vector<int>> res;
     vector<int> ans;
     Helper(res,nums,ans,0);
     return res;
 }