491.递增子序列
思路
本题的关键也是去重，但是与往常不一样的是它无序，所以不能用之前的while方法去重。
使用set容器去重，此时又有一个选择：set为全局变量、set为局部变量
set为全局变量:一直跟随递归进去，即答案中不会有相同的元素,需要不断popset为局部变量：仅在树层中存在，符合去重逻辑，不需要pop
搞清楚set存在的位置，明确set容器基本用法，很简单了。
题解
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums,int start)
{
unordered_set<int> uset;
if(path.size()>=2)
{
res.push_back(path);
}
for(int i = start;i<nums.size();i++)
{
if(!path.empty() && path[path.size()-1]>nums[i])continue;
if(uset.find(nums[i])!=uset.end())continue;
path.push_back(nums[i]);
uset.insert(nums[i]);
backtracking(nums,i+1);
path.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums, 0);
return res;
}
};
46.全排列
思路
第一次遇到排列问题，很显然的不同点就是终止条件+每次for循环从0开始。
例如：nums = [1,2,3]按理来说应当使用used数组，不能选取重复的数值，但是本题有一个前提不含重复数字
我整个活，使用set，问题转变为->不能含有相同的数字，很显然符合set去重的第一种用法（见上题）。
题解
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
unordered_set<int> uset;
void backtracking(vector<int>& nums)
{
if(path.size() == nums.size())
{
res.push_back(path);
return ;
}
for(int i = 0;i<nums.size();i++)
{
if(uset.find(nums[i])==uset.end())
{
path.push_back(nums[i]);
uset.insert(nums[i]);
}
else continue;//注意！！！
backtracking(nums);
uset.erase(nums[i]);//注意set容器在全局变量中要pop，不然越来越大没得玩
path.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
backtracking(nums);
return res;
}
};
47.全排列II
思路
一个大杂烩问题：
- 有重复数字：树层去重
- 全排列问题：树深去重
本题的两个关键点：
- 给定的
nums是一个可包含重复数字的序列，所以意味着set容器不可行，要使用used数组（后面多用这个，更广泛） while(i<nums.size()-1 && nums[i+1] == nums[i])i++这个树层去重逻辑会影响i的值，进而影响used[i] = false。故一定要放在最后！！！这个找了好久好久！！！
题解
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums,vector<bool> used)
{
if(path.size() == nums.size())
{
res.push_back(path);
return ;
}
for(int i = 0;i<nums.size();i++)
{
if(used[i])continue;
used[i] = true;
path.push_back(nums[i]);
backtracking(nums,used);
path.pop_back();
used[i] = false;//!!!重点关注！！！
while(i<nums.size()-1 && nums[i+1] == nums[i])i++;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<bool> used(nums.size(), false);
backtracking(nums,used);
return res;
}
};
332.重新安排行程–待做
51.N皇后–待做
37.解数独–待做
回溯算法总结
补了好多天的回溯，题目做的倒是OK，但总是套着模板做题，里面的递归细节傻傻搞不清，究其原因还是回溯的工程量太大，是无数个for循环的集合！
本章节主要使用回溯解决的问题：
回溯算法能解决如下问题：
- 组合问题：
N个数里面按一定规则找出k个数的集合 - 排列问题：
N个数按一定规则全排列，有几种排列方式 - 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个
N个数的集合里有多少符合条件的子集 - 棋盘问题：
N皇后，解数独等等
对于每类题目，写一下自己的总结感悟：
- 组合问题：最简单也是最经典的问题，for循环遍历树层，回溯遍历树深，收割想要的结果；关键点在于每次递归进入的
for循环起点要不断后移;对于优化：可以针对sum、k等值进行剪枝操作。 - 排列问题：相比组合问题：每次进入回溯
for循环都是从0开始，并且有了树深去重（灵活使用used数组或set容器），对于多点去重：树深+树层，注意搞清逻辑，不要混乱。 - 切割问题：切割问题主要是看收集条件以及把
for循环遍历分割位置（字符串切割）搞清即可。 - 子集问题：子集说实话是组合的一种，不要和排列搞混。就是收集条件放宽了而已。
- 棋盘问题：还在仰望······
回溯复杂度分析——二刷详细看
关于回溯算法的复杂度分析在网上的资料鱼龙混杂，一些所谓的经典面试书籍不讲回溯算法，算法书籍对这块也避而不谈，感觉就像是算法里模糊的边界。
所以这块就说一说Carl的个人理解，对内容持开放态度，集思广益，欢迎大家来讨论！
以下在计算空间复杂度的时候我都把系统栈（不是数据结构里的栈）所占空间算进去。
子集问题分析：
- 时间复杂度：
O(2^n)，因为每一个元素的状态无外乎取与不取，所以时间复杂度为O(2^n) - 空间复杂度：
O(n)，递归深度为n，所以系统栈所用空间为O(n)，每一层递归所用的空间都是常数级别，注意代码里的result和path都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为O(n)
排列问题分析：
时间复杂度：O(n!)，这个可以从排列的树形图中很明显发现，每一层节点为n，第二层每一个分支都延伸了n-1个分支，再往下又是n-2个分支，所以一直到叶子节点一共就是 n * n-1 * n-2 * ..... 1 = n!。
空间复杂度：O(n)，和子集问题同理。
组合问题分析：
时间复杂度：O(2^n)，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。
空间复杂度：O(n)，和子集问题同理。
N皇后问题分析：
时间复杂度：O(n!) ，其实如果看树形图的话，直觉上是O(n^n)，但皇后之间不能见面所以在搜索的过程中是有剪枝的，最差也就是O（n!），n!表示n * (n-1) * .... * 1。
空间复杂度：O(n)，和子集问题同理。
解数独问题分析：
时间复杂度：O(9^m) , m是.的数目。
空间复杂度：O(n^2)，递归的深度是n^2
一般说道回溯算法的复杂度，都说是指数级别的时间复杂度，这也算是一个概括吧！
最后放一个总结图片：
图片来源于 知识星球-莫非毛
终于补完了所有落下的，回归正常刷题了。