力扣每日一题47：全排列

力扣每日一题47：全排列

题目描述：

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],[1,2,1],[2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

通过次数

496.8K

提交次数

757.3K

通过率

65.6%

思路和题解：

这题和第46题全排列的进阶，序列中包含了重复的数字，要求我们返回不重复的序列。我们还是用回溯和思路来做。

我们可以看作是有n个空格，我们要从左往右依次填入题目给定的n个数。我们可以用回溯的方法，依次判断每个位置能填哪些数字，当第n个位置填好后，我们就将当前数组放入答案数组中，递归结束。用一个visited数组时刻标记原始数组的对应位置被选的状态，这样可以避免相同位置的数重复使用。

但是到这里并没有满足题目“全排列不重复”的要求，因为题目给定的序列不同位置的数可能想等，当不同位置的两个相同的数交换位置时会重复。就拿样例1来说，原数组[1,1,2]，第一个1填进第一个空格后，第二个1也能填进第一个空格，这样就重复了。而我们上面做的只保证了第一个1不重复填入第一个空格。所以我们需要处理这个情况。

要解决上面的问题我们需要保证，在填入某个空格（假设是第index个）的时候，我们要保证重复的数字只会被填入这个空格一次即可。我们先将原数组排序，在排好后，相同的数字都相邻。按照原来的步骤走，如果选择要填的数字没有相同的数那就放心地填进去；如果有相同的数字，为了满足值相等位置不相等的数在某个位置只填入一次，我们只能填入重复集合中“从左到右的第一个未被填过的数”，即加一个判断条件if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) { continue; }

代码：

一、回溯

lass Solution {
public:vector<int> visited;void dfs(vector<vector<int>> &ans,vector<int> nums,vector<int> &perm,int depth,int n){if(depth==n){ans.emplace_back(perm);return;}for(int i=0;i<n;i++){//这个位置的数已经填过 或者是 这个位置的前面有相等的数没填过if(visited[i]==1||(i>0&&nums[i]==nums[i-1]&&visited[i-1]==0))continue;//入栈，已选perm.emplace_back(nums[i]);visited[i]=1;//下一层dfs(ans,nums,perm,depth+1,n);//出栈，未选visited[i]=0;perm.pop_back();}}vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),nums.end());vector<vector<int>> ans;vector<int> perm;visited.resize(nums.size());dfs(ans,nums,perm,0,nums.size());return ans;}
};

二、库函数：

class Solution {
public:vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> ans;sort(nums.begin(),nums.end());do{ans.emplace_back(nums);}while(next_permutation(nums.begin(),nums.end()));return ans;}
};