Given a collection of numbers, nums,&nbsp;that might contain duplicates, return all possible unique permutations in any order.

&nbsp;
Example 1:

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


Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 8
	-10 &lt;= nums[i] &lt;= 10


class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) == 1:
            return [[nums[0]]]

        res = self.permuteUnique(nums[1:])

        for i in range(len(res)-1, -1 , -1):
            j = 0
            while j < len(res[i]):
                if res[i][j] == nums[0]: #to account for repeated nums
                    break
                lst = res[i][:]
                lst.insert(j, nums[0])
                res.append(lst)
                j += 1

            res[i].insert(j,nums[0])

        return res
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        boolean used[] = new boolean[nums.length];
        
        permutationsFinder(nums,ans,new ArrayList<>(),used);
        
        return ans;
    }
    
    static void permutationsFinder(int[] nums,List<List<Integer>> ans,List<Integer> list,boolean used[]){
        if(list.size() == nums.length){
            ans.add(new ArrayList<>(list));
            return;
        }
        
        for(int i=0;i<nums.length;i++){
            if(used[i]) continue;
            if(i>0 && nums[i]==nums[i-1] && !used[i-1]) continue;
            list.add(nums[i]);
            used[i] = true;
            permutationsFinder(nums,ans,list,used);
            list.remove(list.size()-1);
            used[i] = false;
        }
    }
}
class Solution {
public:
    void fun(vector<int>& nums, vector<vector<int>>&ans,int i)
    {
        if(i==nums.size())
        {
            ans.push_back(nums);
            return;
        }
        int freq[21]={0};
        for(int j=i;j<nums.size();j++)
        {
            if(freq[nums[j]+10]==0)
            {
            swap(nums[i],nums[j]);
            fun(nums,ans,i+1);
            swap(nums[i],nums[j]);
            }
            freq[nums[j]+10]++;
        }

    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>>ans;
        fun(nums,ans,0);
        return ans;
    }
};
var permuteUnique = function(nums) {
    const answer = []

    function perm (pos, array) {

        if (pos >= array.length) {
            answer.push(array)
        }

        const setObject = new Set()

        for (let index=pos; index<array.length; index++) {
            if (setObject.has(array[index])) {
                continue
            }
            setObject.add(array[index])

            // swap numbers
            let temp = array[pos]
            array[pos] = array[index]
            array[index] = temp

            perm(pos + 1, [...array])

            // undo swapping for next iteration
            temp = array[index]
            array[index] = array[pos]
            array[pos] = temp
        }
    }

    perm(0, nums)

    return answer
};
Permutations II