递归

递归一定要有出口，不然会无限调用，死循环

string fun(int n){if(n==0)return "a";if(n==1)return "b";return fun(n - 1) + fun(n - 2);
}

输出前8种结果：

---

双写数字递归例子

注意递归的return

int doubleNum(int n){if (n < 10){return (10 * n) + n;}else{int a = doubleNum(n / 10);int b = doubleNum(n % 10);return (100 * a) + b;}
}

以：1987为例说明递归顺序，由于每次递归都copy一次函数副本，只有return,才能结束递归的调用。

例子2,不管是谁递归，大小以递归数字为准

string func(string s){if (s.size()==1){return s+=s;//双写}else{string a = func(s.substr(1));//去掉第一个字母string b = func(s.substr(0,s.size()-1));//去掉最后一个字母return a+b;}
}

func(“abc”)结果是：ccbbbbaa

递归判断回文串

bool ishuiwen(string s){//最基本情况，递归出口if (s.size()<=1){//s是单个字符或者空，是回文return true;}else{char first = s[0];char last = s[s.size() - 1];//middle是去掉首位两字符的字符串string middle = s.substr(1, s.size() - 2);return (first == last && ishuiwen(middle));}

打印所有二进制

也就是给定数字n,打印出n的所有可能二进制排列

比如：

n=1 — 0,1

n=2 — 00,01;10,11

n=3 —000,001,010,011;100,101,110,111

…

发现规律：
n=1  {0},{1}
n=2  {00},{01};{10},{11}
n=3  {000},{001},{010},{011}{100},{101},{110},{111}
---所以后一个是前一个所有可能分别加上0和1构成新集合
---也就是n=4是n=3的所有结果，分别插入0和1
n=4
{0 000},{0 001},{0 010},{0 011},{0 100},{0 101},{0 110},{0 111}
{1 000},{1 001},{1 010},{1 011},{1 100},{1 101},{1 110},{1 111}

解：

vector<vector<int> > printfAllBin(int n){//base case,递归结束if(n==0)  return {{}};//递归求结果vector<vector<int>> res=printfAllBin(n-1);//对上一步进行操作得到下一步//这里是对当期的二进制结果前，加0或加1然后存储新结果int size = res.size();//这个是循环结束标志，每次递归res的大小都不同for (int i = 0; i < size;i++){auto tmp = res[i];tmp.push_back(0);//加0res.push_back(tmp);//加一res[i].push_back(1);}return res;
}

vector<vector<int> > printfAllBin(int n){//base case,递归结束if(n==0)  return {{}};//递归求结果vector<vector<int>> res;vector<vector<int>> cur= printfAllBin(n - 1);//cur作为当前res,更新下一次resfor(auto& val:cur){//记录val值后加入1auto tmp = val;tmp.push_back(1);//原有val值加0val.push_back(0);//把结果都装入res中res.push_back(tmp);res.push_back(val);}return res;
}

这里用cur记录当前递归结果，然后加入0和1后，放入res中

子集和问题

78. 子集

求1个数组的子集和

以1，2，3为例

$$\text{顺着思想}f\text{：}$$

f ( { } ) = { } f\left( \left\{ \right\} \right) =\left\{ \right\} f({})={}

f ( { 1 } ) = f ( { } ) + 1 = { } ， { 1 } f\left( \left\{ 1 \right\} \right) =f\left( \left\{ \right\} \right) +1=\left\{ \right\} \text{，}\left\{ 1 \right\} f({1})=f({})+1={}，{1}

f ( { 1 , 2 } ) = f ( { 1 } ) + 2 = { } , { 1 } , { 2 } , { 1 , 2 } f\left( \left\{ 1,2 \right\} \right) =f\left( \left\{ 1 \right\} \right) +2=\left\{ \right\} ,\left\{ 1 \right\} ,\left\{ 2 \right\} ,\left\{ 1,2 \right\} f({1,2})=f({1})+2={},{1},{2},{1,2}

f ( 1 , 2 , 3 ) = f ( { 2 } ) + 3 = { } , { 1 } , { 2 } , { 1 , 2 } , { 3 } , { 1 , 3 } , { 2 , 3 } , { 1 , 2 , 3 } f\left( 1,2,3 \right) =f\left( \left\{ 2 \right\} \right) +3=\left\{ \right\} ,\left\{ 1 \right\} ,\left\{ 2 \right\} ,\left\{ 1,2 \right\} ,\left\{ 3 \right\} ,\left\{ 1,3 \right\} ,\left\{ 2,3 \right\} ,\left\{ 1,2,3 \right\} f(1,2,3)=f({2})+3={},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}

也就是 f ( { 1 , . . , n } ) = f ( { 1 , . . , n − 1 } ) ∪ f ( { 1 , . . , n − 1 } ) 的每一个子集加n \text{也就是}f\left( \left\{ 1,..,n \right\} \right) =f\left( \left\{ 1,..,n-1 \right\} \right) \cup \ f\left( \left\{ 1,..,n-1 \right\} \right) \text{的每一个子集加n} 也就是f({1,..,n})=f({1,..,n−1})∪ f({1,..,n−1})的每一个子集加n

正向解法：

 vector<vector<int>> subsets(vector<int>& nums) {// f({1,..n})=f({1,..,n-1}) U f({1,..,n-1})+nvector<vector<int>> res({{}});for(int i=0;i<nums.size();i++){int n=res.size();//----这个n很重要，限定了当前res的增长for(int j=0;j<n;j++){//现有元素装入resres.push_back(res[j]);//res元素都加上nums[i]res[j].push_back(nums[i]);}}return res;}

递归做法：

一个典型的递归结构:

• [1,2,3] 的子集可以由 [1,2] 追加得出，[1,2] 的子集可以由 [1] 追加得出

• base case 显然就是当输入集合为空集时，输出子集也就是一个空集。

• 递归出口是：{{}}—这里是vector<vector<>>

• 解题关键就是：当前子集和=上一个子集和∪{上一个子集加上多出的元素}

• 也就是：每次从尾部取出一个元素，然后计算当前子集和和该元素的情况

  思维如下：

vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> res;//递归出口if(nums.size()==0)   return {{}};//从尾部减少一个元素int x=nums.back();//减少元素后的集合auto set=nums;set.pop_back();//去掉元素/*当前子集和元素*/for(auto& val:subsets(set)){vector<int> choose_cur =val;choose_cur.push_back(x);//res加入选它的和原来的（不选）res.push_back(val);res.push_back(choose_cur);}return res;}

vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> res;//递归出口if(nums.size()==0) return {{}};//每次去掉nums前面元素int x=nums.front();nums.erase(nums.begin());//去掉x//记录递归子集vector<vector<int>> set=subsets(nums);//回退中：前一个生成后一个的操作for(auto& val:set){auto tmp=val;tmp.push_back(x);//res插入两种情况res.push_back(val);//不选择xres.push_back(tmp);//选择x}return res;}

subsets(set)需要新的变量，不可以直接用res,因为auto遍历，res有push_back操作，会造成死循环

每次从nums去掉前一个或后一个都可以，只要能生成待插值即可

全排列问题

和前面类似，后面的也可以由前面的生成，规律就是：每一个元素插空

比如对d,其中一个子集{c,b,a}中:__c__b__a__,d可以选择__任一处
所以：4乘以{a,b,c}的6种情况，4！=24

难点在于：前一个到后一个的插空

思路：首先原有的一个，直接在最前面插作为结果

​ 然后接下来，从最后一个开始遍历当前字符串，每次插入x后作为结果保存在res中

• 首先先看一个插值方法

void traverse(const vector<vector<int>>& res){for(auto aa:res){for(auto bb:aa){cout << bb << " ";}cout << endl;}
}
int main(){vector<int> nums = {1, 2, 3, 4, 5};vector<vector<int>> res;for (auto it = nums.begin();it<=nums.end();it++){//mm在it位置插入6，此时it指向了新值it = nums.insert(it, 6);//mm放入resres.push_back(nums);//（6）,5,1,2,3,4//mm删除插入新值，不影响下一个插入it=nums.erase(it);//it回到原来的1}traverse(res);return 0;
}

巧用erase和insert，但是记住返回值是下一个迭代器

本题解法：

vector<vector<int>> fullLine(const vector<int>& nums){vector<vector<int>> res;if(nums.size()==0) return {{}};int x = nums.back();//待考虑值vector<int> mm = nums;mm.pop_back();res = fullLine(mm);int n = res.size();for (int i = 0; i < n;i++){auto tmp = res[i];res[i].insert(res[i].begin(), x);//考察插入for (auto it = tmp.end(); it != tmp.begin();it--){it = tmp.insert(it, x);res.push_back(tmp);tmp.erase(it);}}return res;
}

vector<vector<int>> fullLine(const vector<int>& nums){vector<vector<int>> res;if(nums.size()==0) return {{}};int x = nums.back();//待考虑值vector<int> mm = nums;mm.pop_back();auto set = fullLine(mm);for (auto& val:set){auto tmp =val;val.insert(val.begin(), x);res.push_back(val);//考察插入for (auto it = tmp.end(); it != tmp.begin();it--){it = tmp.insert(it, x);res.push_back(tmp);tmp.erase(it);}}return res;
}

前一个靠n来结束循环

后一个res得装所有新的结果

面试题 08.07. 无重复字符串的排列组合

 vector<string> permutation(string S) {vector<string> res;//S.size()==0if(S=="") return {""};//注意是：vector<string>char x=S.back();S.pop_back();res=permutation(S);cout<<x<<endl;int n=res.size();for(int i=0;i<n;i++){auto tmp=res[i];res[i].insert(res[i].begin(),x);for(auto it=tmp.end();it!=tmp.begin();it--){it=tmp.insert(it,x);res.push_back(tmp);tmp.erase(it);}}return res;}

char x=S[0]; res=permutation(S.substr(1));

c++字符串和容器使用完全一致

 vector<string> permutation(string S) {vector<string> res;if(S.size()==0) return {""};//注意是：vector<string>char x=S[0];auto set=permutation(S.substr(1));for(auto& val:set){auto tmp=val;val.insert(val.begin(),x);res.push_back(val);for(auto it=tmp.end();it!=tmp.begin();it--){it=tmp.insert(it,x);res.push_back(tmp);tmp.erase(it);}}return res;}

回溯

嵌套循环与递归回溯

传入nums数组，请选择其中的n个，输出大小为n的所有排列可能

ex: nums={1,2,3}

则n=2的可能：{1，1}，{1，2}，{1，3}，{2，1}，{2，2}，{2，3}，{3，1}，{3，2}，{3，3}

假设n=3时，则迭代写法为：

vector<vector<int>> fun_loop(const vector<int>& nums){vector<vector<int>> res;vector<int> tmp;int n = nums.size();for (int i = 0; i < n;i++){tmp.push_back(nums[i]);for (int j = 0; j < n;j++){tmp.push_back(nums[j]);for (int k = 0; k < n;k++){tmp.push_back(nums[k]);res.push_back(tmp);tmp.pop_back();}tmp.pop_back();}tmp.pop_back();}return res;
}

注意：前一层回到上一层需要放弃前一层所选的元素，不然结果会保留上一次的结果

递归写法：

​ 发现迭代写法的特点，每次for的时候都会放入当前下标的值nums[下标]，然后for结束前，也就是内层循环回退到外层循环时，都需要pop也就是放弃已选的元素。这是天然的递归结构

不过在参数传递上，递归时候：递归的函数拷贝当前结果继续使用，所以必须将重要的参数保留

递归函数参数

• 要么作为全局变量
• 要么作为函数参数传递，为了保留结果，需要指针或引用方式传递

本题需要递归出口和每次需要加元素存储的vector

------递归出口level,也就是嵌套循环层数

------vector tmp,一个符合要求得到结果

vector<vector<int>> res;
vector<vector<int>> fun_recursion(const vector<int>& nums,vector<int> ans,int level){int n = nums.size();for (int i = 0; i < n;i++){//递归出口if(level==3){ans.push_back(nums[i]);res.push_back(ans);ans.pop_back();}//回溯else{ans.push_back(nums[i]);fun_recursion(nums, ans, level + 1);ans.pop_back();}}return res;
}

可以把放元素和放弃元素放在if,else外面

vector<vector<int>> res;//全局变量
vector<vector<int>> fun_recursion(const vector<int>& nums,vector<int> ans,int level){int n = nums.size();for (int i = 0; i < n;i++){//放元素ans.push_back(nums[i]);//递归出口if(level==3){res.push_back(ans);}//回溯else{fun_recursion(nums, ans, level + 1);}//放弃当前元素ans.pop_back();}return res;
}

从结果上来说就是：

当然也可以把全局变量res作为函数参数，但是需要引用&,因为上一层的结果需要保留

vector<vector<int>> fun_recursion(const vector<int>& nums,vector<int> ans,int level,\vector<vector<int>>& res){int n = nums.size();for (int i = 0; i < n;i++){//放元素ans.push_back(nums[i]);//递归出口if(level==3){res.push_back(ans);}//回溯else{fun_recursion(nums, ans, level + 1,res);}//放弃当前元素ans.pop_back();}return res;
}

主函数：

    vector<int> nums = {11, 22, 33};vector<int> mm;vector<vector<int>> it;auto res=fun_recursion(nums,mm,1,it);

这里递归结束没有return，因为level=3这层for是需要的，也可以把level=4作为递归结束条件，放在程序前。

vector<vector<int>> res;
vector<vector<int>> fun_recursion(const vector<int>& nums,vector<int> ans,int level){int n = nums.size();//递归出口if(level==4){res.push_back(ans);return res;}for (int i = 0; i < n;i++){//放元素ans.push_back(nums[i]);//回溯fun_recursion(nums, ans, level + 1);//放弃当前元素ans.pop_back();}return res;
}

全排列问题

嵌套循环

用迭代写法写出只有三个元素的全排列

但是在内层返回外层时候，需要放弃已选择该层元素

int main()
{vector<int> nums = {11, 22, 33};vector<vector<int>> res;// 迭代法求3个元素全排列// 选1；下一个从2，3中选2；最后只能选3for (int i = 0; i < nums.size();i++){vector<int> tmp;tmp.push_back(nums[i]);for (int j = 0; j < nums.size();j++){if(j==i)continue;tmp.push_back(nums[j]);for (int k = 0; k < nums.size();k++){if(k==i || k==j)continue;tmp.push_back(nums[k]);//把符合的结果装入resres.push_back(tmp);//抛去已选的ktmp.pop_back();}//ktmp.pop_back();//回到j前，抛去已选的k}//j}//itraverse(res);return 0;
}

迭代法解决全排列问题只能限定元素个数

比如：10个元素10层循环，而且10个for也解决不聊9个元素的循环

静态性：代码仅局限于一个具体问题的求解，而不是一类问题的求解。

递归回溯

循环嵌套自带有回溯能力，内层循环结束会回到它的上一层循环继续执行。

如何放弃重复的元素不选，也就是直接跳过这次结果，方法：设置标记，如果标记后，for不执行本次结果

vector<bool> flag;
vector<vector<int>> res;
vector<vector<int>> fullLine(const vector<int>& nums,vector<int> ans,int level){int n = nums.size();for (int i = 0; i <n;i++){if(!flag[i]){//放元素ans.push_back(nums[i]);flag[i] = true;//该元素已选择if(level==3){//不再递归res.push_back(ans);}else{//递归fullLine(nums, ans, level + 1);}//放弃元素ans.pop_back();//标志置位未选择flag[i] = false;}}return res;
}

或者设为全局变量

vector<vector<int>> fullLine(const vector<int>& nums,vector<int> ans,int level,\vector<vector<int>>& res,vector<bool> flag){int n = nums.size();for (int i = 0; i <n;i++){if(!flag[i]){//放元素ans.push_back(nums[i]);flag[i] = true;//该元素已选择if(level==3){//不再递归res.push_back(ans);}else{//递归fullLine(nums, ans, level + 1,res,flag);}//放弃元素ans.pop_back();//标志置位未选择flag[i] = false;}}return res;
}

或者：层次大于3时返回结果

vector<vector<int>> res;
vector<bool> flag;
vector<vector<int>> fullLine(const vector<int>& nums,vector<int> ans,int level){int n = nums.size();if(level>3){//结束递归res.push_back(ans);return res;}for (int i = 0; i <n;i++){if(!flag[i]){ans.push_back(nums[i]); //放元素flag[i] = true;//该元素已选择fullLine(nums, ans, level + 1);ans.pop_back(); //放弃元素flag[i] = false; //标志置位未选择}}return res;
}

面试题 08.07. 无重复字符串的排列组合

class Solution {
public:vector<string> permutation(string S) {vector<bool> _flag(S.size(),false);flag=_flag;string str;getPermute(S,str,1);return res;}
private:vector<string> res;vector<bool> flag;//str是一次结果，level是记录层数void getPermute(string S,string str,int level){if(level>S.size()){res.push_back(str);return;//递归结束}for(int i=0;i<S.size();i++){if(!flag[i]){str.push_back(S[i]);flag[i]=true;getPermute(S,str,level+1);str.pop_back();flag[i]=false;}}}
};

• 可以没有level参数，利用str的大小和S的大小

• 可以把递归放在for内，但是没有return;

class Solution {
public:vector<string> permutation(string S) {vector<bool> _flag(S.size(),false);flag=_flag;string str;getPermute(S,str);return res;}
private:vector<string> res;vector<bool> flag;//str是一次结果，level是记录层数void getPermute(string S,string str){for(int i=0;i<S.size();i++){if(!flag[i]){str.push_back(S[i]);flag[i]=true;//装结果if(str.size()==S.size()){res.push_back(str);}//递归else{getPermute(S,str);}str.pop_back();flag[i]=false;}}}
};

子集问题

迭代写法

下一层循环的开始值要+1，因为一个元素只能被一层选择

vector<vector<int>> subSet(const vector<int>& nums){vector<vector<int>> res;res.push_back({});//装入空集vector<int> ans;int n = nums.size();for (int i = 0; i < n;i++){ans.push_back(nums[i]);res.push_back(ans);for (int j = i + 1; j < n;j++){//+1ans.push_back(nums[j]);res.push_back(ans);for (int k = j + 1; k < n;k++){//+1ans.push_back(nums[k]);res.push_back(ans);ans.pop_back();}ans.pop_back();}ans.pop_back();}return res;
}

先添加元素再回溯

注意：前一层选择的元素后一层不能选择，所以下一层的初始值是前一层的i值加一

这里由于i值是递归参数，所以自动递归结束，在i==nums.size()时

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {vector<int> mm;getSubset(nums,mm,0);//下标从0开始return res;}
private:vector<vector<int>> res;void getSubset(vector<int>& nums,vector<int> ans,int index){res.push_back(ans);int n=nums.size();//if(index==n){//   return;//}for(int i=index;i<n;i++){ans.push_back(nums[i]);//加入元素//回溯getSubset(nums,ans,i+1);//i开始值是i+1//放弃当前选择ans.pop_back();}}
};

或者把res填入ans放入for内，只是要提前放入空集

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {res.push_back({});//提前加入空集vector<int> mm;getSubset(nums,mm,0);//下标从0开始return res;}
private:vector<vector<int>> res;void getSubset(vector<int>& nums,vector<int> ans,int index){int n=nums.size();for(int i=index;i<n;i++){ans.push_back(nums[i]);//res.push_back(ans);/*if(index==n-1){}*///回溯//elsegetSubset(nums,ans,i+1);res.push_back(ans);//放在getSubset前后皆可//放弃当前选择ans.pop_back();}}
};

先回溯再加元素

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {vector<int> mm;getSubset(nums,mm,0);return res;}
private:vector<vector<int>> res;void getSubset(vector<int>& nums,vector<int> ans,int index){if(index==nums.size()){res.push_back(ans);return;}//不加入元素getSubset(nums,ans,index+1);//加入元素ans.push_back(nums[index]);getSubset(nums,ans,index+1);//撤销选择ans.pop_back();}
};

总结：

这两种解法实质上是相同的，只是在选择添加子集和进行回溯的时机上有所差异。

• 第一种解法在每次遍历时都会将当前的子集加入到结果集中
• 而第二种解法则是在递归结束时才将当前的子集加入到结果集中

两个解法的 index 的含义基本一致，作用不同。

• 它们都表示后续待选择数组的左边界

  • 解法一index是循环的i+1值

  • 解法二会使用 index 作为判断加入结果集的边界条件。