【Permutations II】cpp

题目：

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].

代码：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
            vector<vector<int> > ret;
            vector<bool> used(nums.size(), false);
            vector<int> tmp;
            Solution::perpermuteUnique(ret, nums, tmp, used);
            return ret;
    }
    static void perpermuteUnique(
        vector<vector<int> >& ret, 
        vector<int>& nums, 
        vector<int>& tmp, 
        vector<bool>& used)
    {
            if ( tmp.size()==nums.size() )
            {
                ret.push_back(tmp);
                return;
            }
            map<int, bool> valueUsed;
            for ( int i = 0; i < nums.size(); ++i )
            {
                if ( used[i] || ( valueUsed.find(nums[i])!=valueUsed.end() && valueUsed[nums[i]] ) ) continue;
                tmp.push_back(nums[i]);
                used[i] = true;
                valueUsed[nums[i]] = true;
                Solution::perpermuteUnique(ret, nums, tmp, used);
                tmp.pop_back();
                used[i] = false;
            }
    }
};

tips：

采用dfs的解法，答题思路与Permutations相同（http://www.cnblogs.com/xbf9xbf/p/4519100.html）

这里的去重的思路就是：重复的值可以出现在排列的不同位置，但是相同的位置上不能出现重复的值。

具体去重的做法是：每一层维护一个map<int, bool>记录在该层，某个值是否被使用了。

 =======================================

第二次过这道题，沿用dfs的思路。

class Solution {
public:
        vector<vector<int> > permuteUnique(vector<int>& nums)
        {
            vector<vector<int> > ret;
            vector<int> tmp;
            vector<bool> used(nums.size(), false);
            Solution::dfs(ret, nums, used, tmp);
            return ret;
        }
        static void dfs(
            vector<vector<int> >& ret, 
            vector<int>& nums,
            vector<bool>& used, 
            vector<int>& tmp)
        {
            if ( tmp.size()==nums.size() )
            {
                ret.push_back(tmp);
                return;
            }
            map<int, bool> valueUsed;
            for ( int i=0; i<nums.size(); ++i )
            {
                if ( used[i] || (valueUsed.find(nums[i])!=valueUsed.end() && valueUsed[nums[i]]) ) 
                    continue;
                tmp.push_back(nums[i]);
                used[i] = !used[i];
                Solution::dfs(ret, nums, used, tmp);
                tmp.pop_back();
                used[i] = !used[i];
                valueUsed[nums[i]] = true;
            }
        }
};