代码随想录算法训练营day 29|第七章 回溯算法part05

本题和大家刚做过的 90.子集II 非常像，但又很不一样，很容易掉坑里。 

代码随想录

视频讲解：回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列_哔哩哔哩_bilibili

这道题本身没那么难想到,但是有很多要注意点:

1. 一旦path的size大于1,就要收集.
2. 使用容器要记住当次for循环已经遍历过的值,这样来去重.可以使用unordered_set(集合),也可以使用数组(提前声明容量为201,然后以每次的数值为下标来验证本次for循环是否已经使用过相等的值),注意如果用数组的话,会更快更方便查找每次是否遍历过,以空间换时间,但是要提前初始化.
3. 每次for循环要判断path内是否有数了,如果有数了那就要判断当前的数值是否不小于最后一个数(也就是最大的那个).

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtracking(vector<int>& nums,int begin){        
        if(path.size()>1){
            res.push_back(path);
        }
        int used[201]={0};
        for(int i=begin;i<nums.size();i++){
            if(path.size()){
                if(nums[i]<path.back()) continue;                
            }
            if(used[nums[i]+100]) continue;
            path.push_back(nums[i]);
            backtracking(nums,i+1);
            path.pop_back();
            used[nums[i]+100]=1;
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        res.clear();
        path.clear();
        backtracking(nums,0);
        return res;
    }
};

46.全排列 

本题重点感受一下，排列问题 与 组合问题，组合总和，子集问题的区别。 为什么排列问题不用 startIndex 

代码随想录

视频讲解：组合与排列的区别，回溯算法求解的时候，有何不同？| LeetCode：46.全排列_哔哩哔哩_bilibili

这道题总体来讲也比较简单,主要注意这几个点:

1. path的收集在它的size恰好等于nums的大小的时候进行,并且需要在这时候直接返回,因为是最终时刻收集结果而不是像上一道题一样边递归边收集.
2. 这时候就需要每次for循环都从0开始,全排列不是顺序收集数字的而是可能跳着收集数字,所以没有递归遍历的规律,但需要每次知道上层递归都已经使用过哪些数,所以要传入used数组来记录已经排列进去的数字.
3. used数组可以直接设置成nums数组大小,因为已经知道nums数组不重复,所以直接可以用该数字的下标来表示它在used数组中的位置,而且for循环内设置先显示用过该数字,递归结束之后再显示没有用过该数字,因为同层递归表示不同的排列顺序,而更深层的递归用来一点一点得到这个顺序的全排列.

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    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;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(),false);
        backtracking(nums,used);
        return res;
    }
};

47.全排列 II 

本题 就是我们讲过的 40.组合总和II 去重逻辑 和 46.全排列 的结合，可以先自己做一下，然后重点看一下 文章中 我讲的拓展内容。 used[i - 1] == true 也行，used[i - 1] == false 也行 

代码随想录

视频讲解：回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II_哔哩哔哩_bilibili