《力扣面试150题》题单拓展——回溯

《力扣面试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.排列序列

数学方法更优秀，通过确定首位数字后面一个有多少种可能，来确定首位的数字，以此类推