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

Solution 1: Use HashMap and DFS recursively solve the problem.

 public class Solution {  
   public List<List<Integer>> permuteUnique(int[] nums) {  
     Map<Integer,Integer> map=new HashMap<>();  
     int n=nums.length;  
     for (int x: nums) {  
       if (map.containsKey(x)) map.put(x,map.get(x)+1);  
       else map.put(x,1);  
     }  
     List<Integer> one=new ArrayList<>();  
     List<List<Integer>> res=new ArrayList<>();  
     dfs(map,0,n,one,res);  
     return res;  
   }  
   private void dfs(Map<Integer,Integer> map, int d, int n, List<Integer> one, List<List<Integer>> res) {  
     if (d==n) res.add(new ArrayList<Integer>(one));  
     else {  
       for (int x: map.keySet()) {  
         int v=map.get(x);  
         if (v>0) {  
           map.put(x,v-1);  
           one.add(x);  
           dfs(map,d+1,n,one,res);  
           one.remove(one.size()-1);  
           map.put(x,v);  
         }  
       }  
     }  
   }  
 }  

Solution 2: Use "next Permutation" method to solve the problem interactively.