代码随想录算法训练营第二十四天| 回溯 491.递增子序列 46.全排列 47.全排列 II

发布时间:2024年01月10日

491. 非递减子序列

?此前通过used数组去重的操作的前提是需要首先给数组排序,本题不可以,因为求递增子序列时,原先的序列并不是一定递增的,此时进行排序后,此时递增子序列会包含其他原先不是原先数据的子序列。

递归参数:index一定是需要的,记录下一层递归分割的起始位置。

递归终止条件:由N叉树可以看出,当子集内个数大于1的时候便可以收获结果

单层搜索的逻辑:在同一树层中,不需要重复读取相同的树,需要对其剪裁,由于不能使用used数组,可以使用哈希判断当前树层是否存在相同的数unordered_set<int> uset; 是记录本层元素是否重复使用,新的一层uset都会重新定义(清空),所以要知道uset只负责本层!还需要判断树枝上的树是否会小于path最后一个数,如果小于了就不是递增子序列了

?

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    void backtracking(vector<int> &nums,int index){
        if(path.size()>1)res.push_back(path);
        unordered_set<int> hash;
        for(int i=index;i<nums.size();i++){
            if(!path.empty()&&nums[i]<path.back()||hash.find(nums[i])!=hash.end())continue;
            hash.insert(nums[i]);
            path.push_back(nums[i]);
            backtracking(nums,i+1);
            path.pop_back();
        }

    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        path.clear();
        res.clear();
        backtracking(nums,0);
        return res;
    }
};

46. 全排列

递归函数参数:首先排列是有序的,也就是说 [1,2] 和 [2,1] 是两个集合,这和之前分析的子集以及组合所不同的地方。可以看出元素1在[1,2]中已经使用过了,但是在[2,1]中还要在使用一次1,所以处理排列问题就不用使用startIndex了。但排列问题需要一个used数组,标记已经选择的元素,如图橘黄色部分所示:

?

?递归终止条件:当收集元素的数组path的大小达到和nums数组一样大的时候,说明找到了一个全排列,也表示到达了叶子节点。

单层搜索的逻辑:排列问题,每次都要从头开始搜索,例如元素1在[1,2]中已经使用过了,但是在[2,1]中还要再使用一次1。而used数组,其实就是记录此时path里都有哪些元素使用了,一个排列里一个元素只能使用一次

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]==true)continue;
            used[i]=true;
            path.push_back(nums[i]);
            backtracking(nums,used);
            used[i]=false;
            path.pop_back();
        }
    }


    vector<vector<int>> permute(vector<int>& nums) {
        path.clear();
        res.clear();
         vector<bool> used(nums.size(), false);
        backtracking(nums,used);
        return res;
    }
};

47. 全排列 II

本题需要进行树层去重操作,树枝去重操作逻辑:当前元素与上一层相等并且use数组的前一个为0(use[i-1]=false),表明是需要进行树层去重, 使用used数组可以将树枝去重和树层区分开来。

同时因为本题需要的是排列问题,i从0开始,为了判断一个元素是否去过,仍然可以使用used数组进行判断。

递归函数参数:used数组与传入nums

?递归终止条件:当收集元素的数组path的大小达到和nums数组一样大的时候,说明找到了一个全排列,也表示到达了叶子节点。

单层搜索的逻辑:排列问题,每次都要从头开始搜索,例如元素1在[1,2]中已经使用过了,但是在[2,1]中还要再使用一次1。而used数组,其实就是记录此时path里都有哪些元素使用了,一个排列里一个元素只能使用一次

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(i>0&&nums[i-1]==nums[i]&&used[i - 1] == false) continue;
            if(used[i]==false){ 
            used[i]=true;
            path.push_back(nums[i]);
            backtracking(nums,used);
            used[i]=false;
            path.pop_back();}
        }

    }


    vector<vector<int>> permuteUnique(vector<int>& nums) {
        path.clear();
        res.clear();
        vector<bool> used(nums.size(),false);
        sort(nums.begin(),nums.end());
        backtracking(nums,used);
        return res;
    }
};

文章来源:https://blog.csdn.net/weixin_47100514/article/details/135497446
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。