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

代码随想录Day25_回溯5_全排列

news 2026/5/12 23:43:08

非递减子序列

问题描述

给了一个数组，要求给出其所有长度>=2的非递减子序列。

思路

压入结果的条件是path.size()>=2，回溯过程结束的条件是移动到了边上startIndex>=num.size()
在树中，非递减序列，要求压入的元素必须比之前压入的大：if(path.empty()||nums[i]>=path.back())

问题

如果给出的数组包含重复元素，那么答案的集合中就会包含重复的数组；

那我标记该位置的元素已经用过了，如何？````

    if(used[i]==false&&(path.empty()||nums[i]>=path.back())){path.push_back(nums[i]);used[i]=true;backtrack(nums,i+1,used);path.pop_back();used[i]=false;}

这样也是不行的，原因在于数组不同下标处的元素可能相等，这样只是标记了一个位置的该元素，但是如果该位置后面的元素和已经遍历过的元素有相同的，也会导致结果集中存在一样的数组。所以重点不是对下标记录，而是对这个元素本身的值进行记录。使用哈希容器unorder_set<int> usedThisLeval

        for(int i=startIndex;i<nums.size();i++){if(usedThisLeval.contains(nums[i])){continue;}if(path.empty()||nums[i]>=path.back()){path.push_back(nums[i]);usedThisLeval.insert(nums[i]);backtrack(nums,i+1);path.pop_back();}}

但是似乎很慢！

原始思路解法代码

class Solution {
public:vector<int>path;set<vector<int>>  res;void backtrack(vector<int>&nums, int startIndex){if(path.size()>=2){res.insert(path);}if(startIndex>=nums.size()){return;}for(int i=startIndex;i<nums.size();i++){if(path.empty()||nums[i]>=path.back()){path.push_back(nums[i]);backtrack(nums,i+1);path.pop_back();}}}vector<vector<int>> findSubsequences(vector<int>& nums) {path.clear();res.clear();backtrack(nums,0);return vector<vector<int>>(res.begin(),res.end());}
};

全排列

题目描述

给定一个不含重复数字的数组，返回其所有可能的全排列。
看到题目第一眼，感觉这道题和之前做过的组合问题很相似。组合问题：在n个数中找K个数的组合。复用后发现不同，N个数的组合在组合问题中是这种情况

在回溯的这颗树中，在移动startIndex的过程中之前的数就不会考虑进来了，但是排列问题需要考虑进来。
解决办法是vector & used标记状态

class Solution {
public:vector<int>path;vector<vector<int>>  res;void backtrack(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]);backtrack(nums,used);path.pop_back();used[i]=false;}}}vector<vector<int>> permute(vector<int>& nums) {path.clear();res.clear();vector<bool>used(nums.size(),false);backtrack(nums,used);return res;   }
};

全排列2

问题理解

数组中出现了重复元素，使用暴力set去重，但是似乎是一种很慢的方法，相当于每次插入都要遍历一次所有组合。

代码

class Solution {
public:vector<int>path;vector<vector<int>>  res;void backtrack(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]==nums[i-1]&&used[i-1]==true){continue;//跳出本次循环}if(used[i]==false){used[i]=true;path.push_back(nums[i]);backtrack(nums,used);path.pop_back();used[i]=false;}}}vector<vector<int>> permuteUnique(vector<int>& nums) {path.clear();res.clear();sort(nums.begin(),nums.end());vector<bool>used(nums.size(),false);backtrack(nums,used);return res; }
};