每日一题——47. 全排列 II

题目链接：47. 全排列 II - 力扣（LeetCode）

代码：

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;

    void traversal(vector<int>& nums,vector<bool> usedy,vector<bool> usedx)
    {
        if(path.size() == nums.size())
        {
            result.push_back(path);
            return ;
        }

        for(int i = 0; i < nums.size(); i++)
        {
            if(usedy[i] == true) continue;
            if( i > 0  && usedx[i-1] == false&& nums[i] == nums[i-1]) continue;
            usedy[i] = true;
            usedx[i] = true;
            path.push_back(nums[i]);
            traversal(nums,usedy,usedx);
            path.pop_back();
            usedy[i] = false;
            usedx[i] = false;
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> usedy(nums.size(),false);
        vector<bool> usedx(nums.size(),false);
        sort(nums.begin(),nums.end());
        traversal(nums,usedy,usedx);
        return result;
    }
};

与全排列1不同的就是这里有重复的数字，因此设计到去重。

去重依然就用树层去重，树枝不去重的原理。

两个相同的树a，b，树枝上可以重复选取，但树层上不行（会产生重复的全排列）。usedx完成此逻辑

一个树a，树枝上不能反复选取，usedy完成此逻辑。

但实际上一个used也就可以完成上面的逻辑，可以看到代码中对usedx和usedy的条件判断是不冲突的。

因此可以合并为：

if(i> 0 && used[i-1] == false && nums[i] == nums[i-1]) continue;  //usedx的逻辑
if(used[i] == true) continue;  //usedy的逻辑

一个used即可实现所有功能