Permitations II

题目：

Given a list of numbers with duplicate number in it. Find all unique permutations.

Example

For numbers [1,2,2] the unique permutations are:

[ [1,2,2], [2,1,2], [2,2,1] ]

接口：

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    vector<vector<int> > permuteUnique(vector<int> &nums) {

    }

};

分析：

Permutation 需要每次dfs从0开始，要么用isUsed确定是否已经插入，要么用find()在vector里面从头到尾找。 由于这题目有重复元素，find的方法不好使，就用isUsed按照套路来就可以

注意，find()和sort()都在#include algorithm里面

INT_MIN和INT_MAX在#include limits里面，具体名字记不清楚了。

解法：

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    void dfs(vector<int> nums, 
                vector<int> instance, 
                vector<bool>& isUsed, 
                vector<vector<int> >& results) {

        if (instance.size() == nums.size() ) {
            results.push_back(instance);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (isUsed[i] == true) {
                continue;
            }

            if (i != 0 && nums[i] == nums[i - 1] && isUsed[i - 1] == false) {
                continue;
            }

            instance.push_back(nums[i]);
            isUsed[i] = true;
            dfs(nums, instance, isUsed, results);
            isUsed[i] = false;
            instance.pop_back();

        }

    } 

    vector<vector<int> > permuteUnique(vector<int> &nums) {
        if (nums.size() == 0) {
            return vector<vector<int> >();
        }

        vector<vector<int> > results;
        vector<int> instance;
        vector<bool> isUsed(nums.size(), false);

        sort(nums.begin(), nums.end() );

        dfs(nums, instance, isUsed, results);

        return results;
    }

};