47. 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],
  [2,1,1]
]

Analysis:

DFS, to avoid duplicate solution, we can make sure at each position, we dont use duplicate elements. so each recursion create a new HashSet<Integer> to accomplish this.

Complexity:

Time: O(N!)

Space: O(N)

Code:

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> returnList = new ArrayList<List<Integer>>();
        if(nums == null || nums.length == 0){
            return returnList;
        }

        dfs(new ArrayList<Integer>(), nums, returnList, 0);
        return returnList;
    }

    private void dfs(List<Integer> tempList, int[] nums, List<List<Integer>> returnList, int pos){
        if(tempList.size() == nums.length){
            returnList.add(new ArrayList<Integer>(tempList));
            return;
        }

        Set<Integer> used = new HashSet<Integer>();
        for(int i = pos; i < nums.length; i++){
            if(!used.contains(nums[i])){
                used.add(nums[i]);
                swap(pos, i, nums);
                tempList.add(nums[pos]);
                dfs(tempList, nums, returnList, pos+1);
                tempList.remove(tempList.size() -1);
                swap(pos, i, nums);
            }
        }
    }

    private void swap(int a, int b, int[] nums){
        if(a != b){
            int temp = nums[a];
            nums[a] = nums[b];
            nums[b] = temp;
        }
    }
}