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

全排列问题(包含重复数字与不可包含重复数字)

news 2026/6/2 3:13:38

首先对于不可重复排列的序列，只需要使用标准的回溯法即可：

vector<int> vis; void backtrap(vector<int>& nums, vector<int>& res, vector<vector<int>>& con, int i){ if(i==nums.size()){ con.push_back(res); return; } for(int j =0;j<nums.size();++j){ if(vis[j]) continue; res.push_back(nums[j]); vis[j]=1; backtrap(nums,res,con,i+1); vis[j]=0; res.pop_back(); } } class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vis.resize(nums.size(),0); vector<int> res; vector<vector<int>> con; backtrap(nums,res,con,0); return con; } };

注意事项：
在back函数中，当前迭代深度和for循环的代数的表示一定要不一样，一个是i，那么另一个就是j，一定要区分！！！！我就踩这个坑了。

但是该方法对于可以包含重复数字的序列就不管用了，如果继续用这个方法，那么会导致出现许多重复的解。怎么办呢？为避免在包含重复元素的排列问题中产生重复解，采用「排序 + 访问状态约束」的方法。具体做法是：先对原序列进行排序，使相同元素相邻；在回溯选择元素时，若当前元素与前一个元素相同且前一个元素尚未被使用，则跳过当前元素，从而保证相同元素在排列中的相对选择顺序一致，避免生成重复排列。

class Solution { vector<int> vis; public: void backtrack(vector<int>& nums, vector<vector<int>>& ans, int idx, vector<int>& perm) { if (idx == nums.size()) { ans.emplace_back(perm); return; } for (int i = 0; i < (int)nums.size(); ++i) { if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && vis[i - 1])) { continue; } perm.emplace_back(nums[i]); vis[i] = 1; backtrack(nums, ans, idx + 1, perm); vis[i] = 0; perm.pop_back(); } } vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> ans; vector<int> perm; vis.resize(nums.size()); sort(nums.begin(), nums.end()); backtrack(nums, ans, 0, perm); return ans; } };