# 47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

# Solution

Approach 1: DFS with hash table.

# Code (Python)

Approach 1:

# Code (C++)

Approach 1:

class Solution {
private:
    vector<vector<int>> res;
    void permuteUnique(vector<int>& nums, int head) {
        if (head == nums.size())
        {
            res.push_back(nums);
            return;
        }
        unordered_set<int> visited;
        for (int i = head; i < nums.size(); ++i)
        {
            if (visited.find(nums[i]) != visited.end())
                continue;
            visited.insert(nums[i]);
            if (i > head)
                std::swap(nums[head], nums[i]);
            permuteUnique(nums, head + 1);
            if (i > head)
                std::swap(nums[head], nums[i]); // need to swap back.
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        permuteUnique(nums, 0);
        return res;
    }
};