【算法——递归回溯】
这个东西还是很重要的，直接决定了你的动态规划章节的学习深度
都是一类题，换汤不换药。快去ac
1. 子集 II 2. 全排列 3. 全排列 II 4. 子集 5. 字母大小写全排列 6. 组合 7. 组合总和 8. 组合总和 II 9. 组合总和 III
递归的本质就是大问题转换为小问题
78. 子集
方法1：
vector<vector<int>>V; //答案集
void dfs(vector<int>nums, vector<int>v, int index)
{V.push_back(v); //每个节点都收集for (int i = index; i < nums.size(); i++) {//当前数追加v.push_back(nums[i]);//开始当前数后面的组合 生成子问题dfs(nums, v, i + 1);v.pop_back();}}方法2：
算法讲解038【必备】常见经典递归过程解析_哔哩哔哩_bilibili
vector<vector<int>>V; //答案集
//size代表我们当前的路径
void dfs(vector<int>nums, vector<int>v, int index,int size)
{//每次收集都在叶子节点 收集v的前size个if (index >= nums.size()) {vector<int>k;for (auto i = v.begin(); i < v.begin() + size; i++)k.push_back(*i);V.push_back(k);}else{v[size] = nums[index];dfs(nums, v, index + 1, size + 1); //增加路径，当前数选择dfs(nums, v, index + 1, size); //当前数不加入路径，但是index任然+，为了收集子集}
}90. 子集 II
注意要sort排序
方法1：
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<algorithm>
using namespace std;//首先这个子集问题有重复元素，我们在每一个节点就收。
//会出现V中有重复的情况（简单一点就是直接用set代替vector）
//还有一种方法就是用一个和nums等长的bool数组
//说这个bool前，自己画一下{1,2,2}的树形图vector<vector<int>>V;
void dfs(vector<int>v,vector<int>nums, int index,vector<bool>bol)
{V.push_back(v);for (int i = index; i < nums.size(); i++){//bool分析：//首先不能越界(i>0保护)//怎么判断是在判断是在当前树枝还是树层重复（画一下树形图，我这句话就不再抽象）//!bol[i-1]&&nums[i]==nums[i-1]就是前一个数没有选,并且当前和前一个相等。//什么时候会出现这种情况，自然是同一个树层。if (i > 0 && nums[i] == nums[i - 1] && !bol[i - 1]){//break; //这里要注意不能是break，这里发现重复就跳跃这个数，往后面 continue;}v.push_back(nums[i]);bol[i] = 1;dfs(v, nums, i + 1,bol);v.pop_back();bol[i] = 0;}}int main()
{vector<int>nums = { 1,2,1,2 };sort(nums.begin(), nums.end()); //注意要排序vector<bool>bol(nums.size());dfs({}, nums, 0,bol);for (auto i : V){for (auto j : i)cout << j << " ";cout << endl;}return 0;
}方法2：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;vector<vector<int>>V;void dfs(vector<int>nums, vector<int>path, int index, int size)
{if (index >= nums.size()){vector<int>k;for (auto i = path.begin(); i < path.begin() + size; i++)k.push_back(*i);V.push_back(k);}else{path[size] = nums[index];dfs(nums, path, index+1, size + 1);int j = index;while (j < nums.size() && nums[j] == nums[index]){j++;}dfs(nums, path, j, size );}}int main()
{vector<int>nums = { 1,1,2,2 };dfs(nums, vector<int>(nums.size()), 0, 0);for (auto i : V){for (auto j : i)cout << j << " ";cout << endl;}return 0;
}方法3：
算法讲解038【必备】常见经典递归过程解析_哔哩哔哩_bilibili
vector<vector<int>>V; //答案集
//size代表我们当前的路径
void dfs(vector<int>nums, vector<int>path, int index,int size)
{if (index >= nums.size()){vector<int>k;for (auto i = path.begin(); i < path.begin() + size; i++)k.push_back(*i);V.push_back(k);}else{int j = index + 1;while (j < nums.size() && nums[j] == nums[index]) //j直到遍历到下一组数的第一个j++;//这里后面就有点模糊了，需要刻意练习dfs(nums, path, j, size); //从一组数第一个开始重复的操作 ；直到j超出，然后上面就会把{}空集，加入Vfor (; index < j; index++){path[size++] = nums[index];dfs(nums, path, j, size); //这个控制当前组合}}
}
46. 全排列
无重复
方法1： 常规回溯
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;vector<vector<int>>V;void dfs(vector<int>nums, vector<int>path,vector<bool>bol)
{if (path.size() == nums.size()){V.push_back(path);return;}for (int i = 0; i < nums.size(); i++){if (bol[i]) continue;path.push_back(nums[i]);bol[i] = 1;dfs(nums, path,bol);path.pop_back();bol[i] = 0;}}int main()
{vector<int>nums = { 1,2,3 };dfs(nums, {},vector<bool>(nums.size()));for (auto i : V){for (auto j : i)cout << j << " ";cout << endl;}return 0;
}方法2：交换法
i就是当前所指的位置；含义是：后面的数都要和i换一下。j>=i，也就是控制其他数和i交换。注意要换回，因为操作的是一块数组。
实在不明白，举个例子（1,2,3,4,5）看看前5行，就知道这个递归在讲什么了。
清理现场思想：算法讲解038【必备】常见经典递归过程解析_哔哩哔哩_bilibili
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;vector<vector<int>>V;
void dfs(vector<int>nums,int i)
{if (i == nums.size())V.push_back(nums);elsefor (int j = i; j < nums.size(); j++){swap(nums[i], nums[j]);dfs(nums, i + 1);swap(nums[i], nums[j]);}
}47. 全排列 II
有重复
交换法，加一个set记录
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;vector<vector<int>>V;
void dfs(vector<int>nums,int i)
{if (i == nums.size())V.push_back(nums);else{set<int>has;for (int j = i; j < nums.size(); j++){//nums[j]没有来过i位置才会尝试if (has.find(nums[j]) == has.end()){has.insert(nums[j]);swap(nums[i], nums[j]);dfs(nums, i + 1);swap(nums[i], nums[j]);}}}}栈排序（递归）:
算法讲解038【必备】常见经典递归过程解析_哔哩哔哩_bilibili
#include<iostream>
#include<stack>
#include<vector>
using namespace std;void print(stack<int>sta) //打印stack
{while (!sta.empty()){cout << sta.top() << " ";sta.pop();}
}int deep(stack<int>sta) //获得深度
{if (sta.empty())return 0;sta.pop();return deep(sta) + 1;
}//返回dep深度里面的最大值
int maxsta(stack<int>sta,int dep) //找最大值
{if (!dep)return INT_MIN;int max_ = sta.top();sta.pop();max_ = max(max_, maxsta(sta,dep - 1));return max_;
}int maxsta_len(stack<int>sta,int dep,int maxsta) //找最大值的个数
{if (dep==0)return 0;int num = sta.top();sta.pop();return (num == maxsta ? 1 : 0) + maxsta_len(sta, dep - 1, maxsta);
}//最大值沉底
void down(stack<int>&sta, int max, int dep, int k)
{if (dep == 0)for (int i = 0; i < k; i++)sta.push(max);else{int num = sta.top();sta.pop();down(sta, max, dep - 1, k);if (num != max)sta.push(num);}}void sor(stack<int>&sta) //排序
{int dep = deep(sta);while (dep > 0){int max = maxsta(sta,dep);int k = maxsta_len(sta,dep, max);down(sta, max, dep, k);dep -= k;}
}int main()
{stack<int>sta;auto j = { 7,1,3,6,6,4,5,2 };for (auto i : j)sta.push(i);cout << "排序前:" << endl;print(sta); //排序前输出cout << endl;sor(sta);cout << "排序后:" << endl;print(sta);return 0;
}汉诺塔：
记住：没有所谓的左中右，只有from（起点），to（到哪里），other（其他）
#include<iostream>
#include<vector>
using namespace std;void dfs(int i,string from,string to,string other)
{if (i <= 0)return;if (i == 1)cout << "1 from " << from << " to " << to << endl;else{//目标：整体 左 to 右 ； 那么 i-1 先 左 to 中 完成最底下最大的盘OK了dfs(i - 1, from, other, to);cout << i << " from " << from << " to " << to << endl;//然后再去实现i-1从中到右的递归 这个过程中又会出现很多相对的“最大盘”。dfs(i - 1, other, to, from);}}int main()
{int n = 3;dfs(n, "左", "右", "中");return 0;
}