《力扣面试150题》题单拓展——回溯
1.基础知识
void find(string &s, int i, string &path){
//终止条件
if(i == s.size()){
ans.push_back(path);
return;
}
for(int k=0; k<index[sub].size(); k++){ //处理一层
path.push_back(index[sub][k]);
find(s, i+1, path); //递归
path.pop_back(); //回溯的关键
}
}
//本层的循环处理一层，递归去处理下一层
2.标准回溯
17.电话号码的字母组合
很标注规范的回溯
39.组合总和
每个数字都可以重复用，所以每层递归并不一定都会向下走一位，而是原地位进去，sum是返回条件
for(int index=i; index<9; index++){
if(sum+nums[index] <= n) //剪枝
find(index, ...);
77.组合
把第一层函数当做一层展开，就是用for循环，展开一层遍历，用递归去向下延伸
for(int index=i; index<nums.size(); index++)
这里的终止条件时path收集到了几位
78.子集
当前位要或者不要，这里就没有for循环了，因为直接就可以分为两种情况进行展开了
3.特殊去重
40.组合总和II
终止条件有sum控制，结果集长度不一定相同
if(j-i>0 && nums[j] == nums[j-1])
//j-i>0 保证了不会和上一层的重复，而且去重的还是本层的 去重本层，但不去重递归的深层
continue;
216.组合总和III
终止条件有sum和len控制
剪枝+下一位的位数
for(int index=i; index<9; index++){
if(sum+nums[index] <= n){
path.push_back(nums[index]);
find(index+1, n, k, path, len+1, sum+nums[index]); //递归进入当前遍历位的下一位
path.pop_back();
}
}
377.组合总和IV
回溯法翻车了！！！！
优秀评论：转为爬楼梯的问题，每次爬的层数是从nums里面选出来的，太秀了
for(int i=1; i<=target; i++){
for(auto num:nums){
if(i >= num)
dp[i] += (long long)dp[i-num];
}
}
46.全排列
不重复数组，借助辅助数组来表示是否加入到path中，回溯即可
47.全排列II
全排列，从没选过的里面选一个，结果集长度一定一样，所以终止条件用len判断，去重用bool来判断
回溯时的剪枝很优秀，相比如让每个元素都来i位，更好理解
// 1 1 2 现在需要剪枝同一层的第二个1收集的答案
//当第一个1没有被使用的时候，遍历到第二个1，一定要去重
//如果第一个1现在已经被使用了，那么就可以不再去重，第二个1可以继续使用
if(flag[i] == false)
if(i>0 && nums[i]==nums[i-1] && flag[i-1] == 0) //这样可以避免子层的剪枝
90.子集II
这个题值得特殊对待，挑选构成组合问题，不是排列并且没有sum来当做终止条件
因为没有终止条件，每次进入递归都会保存，所以不要把他想象成第i位取不取，而是看做一个集合，从集合里面取不取这个数字加入到结果集合中
void find(vector<int>&nums, int i, vector<int>&path){
ans.push_back(path); //这里相当于不要i位，直接先保存
for(int k=i; k<nums.size(); k++){ //这里就是带挑选的集合
if(k>i && nums[k]==nums[k-1])
continue;
path.push_back(nums[k]); //这里为要k位，
find(nums, k+1, path);
path.pop_back();
}
}
22.括号生成
根据左右括号的数量，去确定是否参与递归，这题自己思路完美！！
那评论区都在噶什么，那么多动态规划
4.特例
60.排列序列
数学方法更优秀，通过确定首位数字后面一个有多少种可能，来确定首位的数字，以此类推
