leetcode47. 全排列 II

思路

对比46题，这里有重复数字，[1，2，2]中[1，2，2]和[1,2,2]是相同的，可以将数组排序，然后遇到相同数字时，判断上一个数字是否已经用过，如果用过了，那么就跳过这次循环（相当于去重）。

class Solution {
public:
    vector<vector<int>>res;
    vector<int>path;
    bool flag[10];
    void dfs(vector<int>& nums,int u){
        int n=nums.size();
        if(u==n)res.push_back(path);
        for(int i=0;i<n;i++){
            if(i>0&&nums[i]==nums[i-1]&&flag[i-1])
                continue;
            if(!flag[i]){
                flag[i]=true;
                path.push_back(nums[i]);
                dfs(nums,u+1);
                flag[i]=false;
                path.pop_back();
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        dfs(nums,0);
        return res;
    }
};