Leetcode/LinkedIn,微软--47. Permutations II(backtracking)

47. Permutations II（backtracking）

• Difficulty: Medium

https://leetcode.com/problems/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]
]

思路： DFS. 1. use boolean[] to indicate is current # is added to path
                    2. sort Array to skip repeated path by only adding duplicats if pre # is added to path.
Complexity: O(N!)

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        boolean[] used = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(res,new ArrayList<Integer>(),nums,used,0);
        return res;
    }
    public void dfs(List<List<Integer>> res,List<Integer> path,int[] nums,boolean[] used,int level){
        if(level==nums.length){
            res.add(new ArrayList(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(used[i])continue;//num is used
            //when adding duplicates, we make sure pre num is added to path, else repeadted path 
            if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
            path.add(nums[i]);//i element placed in current level
            used[i] = true;//marked used
            dfs(res,path,nums,used,level+1);
            path.remove(path.size()-1);//return to last decision point
            used[i] = false;
        }
    }
}

思路： Use HashMap to track each element's count, dfs with array no duplicates, keep adding till reach end (count = 0). If count = 0, means current digits are fully added to solution.
https://www.youtube.com/watch?v=nYFd7VHKyWQ
Instead of using arr, we can sort nums and skip duplicates in dfs

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();//map to record count of each element
        for(int n:nums){
            if(!map.containsKey(n))map.put(n,1);
            else map.put(n,map.get(n)+1);
        }
        int[] arr =new int[map.size()];//arr is the version of nums w/o duplicates
        int i =0;
        for(Integer key:map.keySet()){
            arr[i] = key;
            i++;
        }
        dfs(res,new ArrayList<Integer>(),arr,map,0,nums.length);
        return res;
    }
    public void dfs(List<List<Integer>> res,List<Integer> path,int[] nums,HashMap<Integer,Integer> map,int level,int len){
        if(level==len){
            res.add(new ArrayList(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(map.get(nums[i])==0){
                continue;
            }
            path.add(nums[i]);//i element placed in current level
            map.put(nums[i],map.get(nums[i])-1);//marked used
            dfs(res,path,nums,map,level+1,len);
            path.remove(path.size()-1);//return to last decision point
            map.put(nums[i],map.get(nums[i])+1);
        }
    }
}