当前位置：首页 > article >正文

【代码随想录|回溯算法排列问题】

article 2024/11/20 15:00:59

491.非减子序列

题目链接. - 力扣（LeetCode）

这里和子集问题||很像，但是这里要的是非递减的子序列，要按照给的数组的顺序来进行排序，就是如果我给定的数组是[4,4,3,2,1]，如果用子集||的做法先进行排序得到[1,2,3,4,4]，那我就会收集得到[1,2][2,3][3,4][4,4]等等子集，但是这道题的话我得到的集合只有[4,4]，就是这里我只从我给的数组里进行排序，给非递减的子集。

去结点操作：

一、进行树层去重

但是用之前的方法排序后看used数组里面我两个元素到底用没用已经不可行了，所以这里加了一个set数组，来进行去重，只要我没有和之前相同的元素那就继续取

（这里不用回溯掉used 我觉得是之前回溯是因used定义是在主函数里面，你不手动回溯那个值不会主动变为0，而这里直接定义函数里，在每一层循环外面，我一进去递归就重开了一个set数组，天然的就不用进行回溯了）

二、去掉递减的结点

去结点的时候，我们把我们遍历到的节点和收集到的结点进行比较，如果这个节点比我们收集到的结点小了，那么我们硬塞进去就不是递增序列了，所以直接continue进行收集下一个结点。

class Solution {
public:
vector<int>path;
vector<vector<int>> result;
void backtracing (vector<int>& nums,int startindex){
    if(path.size()>1){
        result.push_back(path);//子集在2到2以上再进行收集
    }
    unordered_set<int> used;//每一层都会重置used
    for(int i=startindex;i<nums.size();i++){
        if(!path.empty()&&nums[i]<path.back()||used.find(nums[i])!=used.end()){
            continue;//去掉要进行递减的结点和树层去重
        }
        path.push_back(nums[i]);
        used.insert(nums[i]);//把nums[i]的值放used里面好进行判断到底用没用过
        backtracing (nums,i+1);
        path.pop_back();
    }
}
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracing (nums,0);
        return result;
    }
};

46.全排列

题目链接https://leetcode.cn/problems/permutations

要求是同一个数不能重复选取嘛，所以要用到used数组

这个是排列问题，需要返回和传进来数组大小相等的全排列数组，所以排列问题就不用设置startindex了，因为不用对前面的数进行去重，但是要设置一个used数组，不能重复选择同一个元素。

class Solution {//正确代码
public:
vector<int>path;
vector<vector<int>>result;
 void backtracking(vector<int>& nums,vector<bool>used){
    if(path.size()==nums.size()){
        result.push_back(path);
        return;
    }
    for(int i=0;i<nums.size();i++){
        if(used[i]==true){//用过的数就跳过
            continue;
        }
        path.push_back(nums[i]);
        used[i]=true;
        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 result;
    }
};

注意这里只能是递归到used数组为true的时候continue进行下一次选取，如果像我一样直接对used等于0来进行判断的话，那它等于1的时候就不会有限制，就会一直进行递归进行循环，直到栈空（离大谱..）

for(int i=0;i<nums.size();i++){//错误代码
        if(used[i]==false){
            path.push_back(nums[i]);
            used[i]=true;
        }
        backtracking(nums,used);
        path.pop_back();
        used[i]=false;
    }

47.全排列||

题目链接https://leetcode.cn/problems/permutations-ii

这道题和46.全排列不太一样的就是这里给的nums数组有重复值，比如nums给[1,1,2]，那么如果我按没有重复数的做法来做的话就会有两个[1,1,2]，那这里就是不允许的，所以我们要在上一道题的基础上多进行一次去重，就是像组合问题一样进行树层去重，同一树层上的数continue不再选取。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& nums, vector<bool> used) {
        if (nums.size() == path.size()) {
            result.push_back(path);//到了nums大小就收集到result，然后返回
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)
                continue;//树层去重
            if (used[i] == true)//选过的不再重复选
                continue;
            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, used);
            used[i] = false;
            path.pop_back();
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());//把nums排序used数组好进行比较进行树层去重
        backtracking(nums, used);
        return result;
    }
};

查看全文

http://www.kler.cn/a/401651.html