047 - Permutations II

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
Hide Tags
Backtracking
Hide Similar Problems
(M) Permutations
这题是 046 – Permutations 的follow up，就复杂在允许重复的值，但不允许重复的结果。
这跟 090 – Subsets II 的要求非常相似，但要复杂一点：这里的值不光重复，还是乱序的，可能隔几个，再来重复前面的值。
因此，要用 090 同样的思路，就得要另外加个数组表示是否要skip某个数字（该数字第一组处理完之后，即置为要skip）。
如果不想加，那就先sort，然后只需要用 090 – Subsets II 同样的思路，放在回溯的递归调用之后，就可以了。
跑的结果，先sort 是 36 ms，加上skip数组是40 ms，看起来很接近。
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> rst;
        int sz=nums.size();
        if(sz)
        {
            vector<int> buf;
            vector<bool> used(sz, false);
            sort(nums.begin(), nums.end());
            build(nums, sz, used, 0, buf, rst);
        }
        return rst;
    }
   
    void build(vector<int>& nums, int sz,
                vector<bool>& used, int count,
                vector<int>& buf, vector<vector<int>>& rst)
    {
        //masked codes are for skipping, open it if do skipping.
        //unordered_map<int, bool> skip;
        for(int ii=0; ii<sz; ++ii)
        {
            int data=nums[ii];
            if((false==used[ii]))  /*&& (false==skip[data]*/ ))
            {
                used[ii]=true;
                buf.push_back(data);
                if(count==sz-1)
                    rst.push_back(buf);
                else
                    build(nums, sz, used, count+1, buf, rst);
                buf.pop_back();
                used[ii]=false;
               
                //skip[data]=true;
                while(ii<sz-1 && nums[ii+1]==data)
                    ii++;
            }
        }
    }
};
36 ms, 40 ms.