题目描述

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

样例

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

dfs

class Solution { // 代码参考yxc
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> st;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        st = vector<bool>(nums.size(),false);
        path = vector<int>(nums.size());
        dfs(nums, 0, 0);
        return ans;
    }

    void dfs(vector<int>& nums, int u, int start){
        if(u == nums.size()) // u 表示当前位置  start 表示从哪里开始枚举数字
        {
            ans.push_back(path);
            return;
        }

        for(int i=start;i<nums.size();i++)
        {
            if(!st[i])
            {
                st[i] = true;
                path[i] = nums[u];
                if(u+1<nums.size() && nums[u+1]!=nums[u]) // 如果下一个数字和当前数字不重复，则从0开始
                    dfs(nums, u+1, 0);
                else dfs(nums,u+1,i+1); // 下一个数字和当前数字重复，人为排序，从下一个开始
                st[i] = false;

            }
        }
    }
};