递归思想总结--排列组合为例

全排列的递归实现

原问题分解：1234全排列，234全排列，34全排列，4全排列，显然是递归思想，而解决方法是交换（从第一个数字起，将它与其后面的每个数字进行交换，swap(array[idx], array[i]);）用for：1：n来控制这个分解过程。

递归程序需要至少一个变量来控制递归执行的深度，这里，用idx来表示这个变量,表示当前递归时元素的索引（index）。

至于终止条件，当然是idx指向最后一个元素时为止，假如元素有n个，那么i=n就是
递归的终止条件，此时就得到了一组排列，将该组排列输出即可，如1234，1243，1324，1342etc

由于需要变量i来控制递归的执行，需要元素个数n来获得递归终止条件，当然需要
一个数组或指针来获得所有元素，所以递归程序的函数可以写为：

get_all_permutation(Type* array, int idx, int n)

终止条件为：

if (idx==n-1)
  print(array);

写出递归的函数头和终止条件，递归程序就可以说是完成了一半，明确用哪个变量来控制递归的过程，用哪个变量控制递归的深度和什么时候该结束递归。弄明白这些就可以写执行递归的代码了。

for (int i=idx; i<n; ++i) {
    // 将第idx个元素依次与后面的元素进行交换
    swap(array[idx], array[i]);
    // 递归得到idx后面的元素的全排列
    get_all_permutation(array, idx+1, n);

}
// 注意：错误代码！！

此时，貌似整个代码完成了，但注意每次递归中，数组a中的元素所处位置都在变化，这样，回退
到上一层执行从第一个数字起，将它与其后面的每个数字进行交换这一步就得不到满足了，因此在每次循环中执行递归返回后，我们需要再次交换元素的位置，用以使数组a恢复原样。

for (int i=idx; i<n; ++i) {
      // 将第idx个元素依次与后面的元素进行交换
      swap(array[idx], array[i]);
      // 递归得到idx后面的元素的全排列
      get_all_permutation(array, idx+1, n);
      // 在递归结束回退时恢复数组，确保下一次循环的正确执行
      swap(array[idx], array[i]);
  }
  // 正确代码！！

递归解组合问题

核心操作temp.push_back(i);，用for：1：n来控制这个组合问题求解过程。

num来控制递归执行的深度

终止条件，当前组合个数num==k(需要组合个数)

同理，递归退出进入下一层for循环时恢复原样temp.pop_back();

所以递归程序的函数参数可以写为：
void combine(vector<vector<int> > &res,vector<int> &temp,int start,int num,int n ,int k)

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> >res;
        if(n<k)return res;
        vector<int> temp(0,k);
        combine(res,temp,1,0,n,k);
        return res;
    }
    void combine(vector<vector<int> > &res,vector<int> &temp,int start,int num,int n ,int k){
        if(num==k){
            res.push_back(temp);
            return;
        }
        for(int i = start;i<=n;i++){
            temp.push_back(i);
            combine(res,temp,i+1,num+1,n,k);
            temp.pop_back();
            }
        }
};

部分用到了回溯法的思想，即我们抽取第一个字符，然后从后面n-1个字符中抽出k-1个；抽取第二个字符，再从后面的n-2个字符抽出m-1个……这样循环下去。因为这样的操作每次都是往后进行寻找的，所以不用考虑去重的问题。