题目内容

给定一个可包含重复数字的序列 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、1 <= nums.length <= 8
2、-10 <= nums[i] <= 10

题解

本题有两种考虑的方式，一种是考虑枚举每个位置可以填哪些数字，然后进行枚举；另一种是枚举每个数填到哪些位置上。这里说个题外话，若题目中给出字典序输出的要求时，尽量选择第一种考虑方式求解，这样可以尽量保证开头位置从小往大枚举。

回到本题，与上题的不同之处在于，其中内含相同元素，这样就存在枚举的全排列中可能会出现重复情况，因为上题的代码将所有的待选元素考虑为不同的元素，这里相同的元素也会考虑为不同的元素，因此需要思考如何避免这种情况就可以把这道题写出来了。

这里给出一个解决方案，即在每一次的排列中，保证相同的元素的相对位置保持不变即可。

比如：有3个相同的1，姑且认为是1’,1’’,1’’’,nums=[1,1,1,2],那么全排列如下：

ans = [[1’,1’’,1’’’,2],[1’,1’’,2,1’’’],[1’,2,1’’,1’’’],[2,1’,1’’,1’’’]]

我们仍然延续上一题的深度优先算法的思想，具体实现，请看代码解释。

代码

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> st;

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        //保证相同元素的相对顺序不变就可以。每次枚举第一个没有用过的相同的数字。

        sort(nums.begin(),nums.end());//为了将相同的元素放到一起
        path = vector<int>(nums.size());
        st = vector<bool>(nums.size());

        dfs(nums,0);
        return ans;
    }

    void dfs(vector<int>& nums, int u){
        if(u == nums.size()){
            ans.push_back(path);
            return;
        }

        for(int i = 0; i < nums.size(); i++){
            //当该数没有被用过，且前一个数和本数相同，且保证前一个数已经用过，那么就可以使用这个数
          	if(st[i] == false){
                if(i && nums[i] == nums[i - 1] && st[i - 1]) continue;
                st[i] = true;
                path[u] = nums[i];
                dfs(nums,u + 1);
                st[i] = false;
            }
        }
    }
};