Share my solution with backtracking and a HashMap


  • 0
    public List<List<Integer>> permuteUnique(int[] nums) {
            if(nums.length==0){
                return new ArrayList<List<Integer>>();
            }
            HashMap<Integer, Integer> count = new HashMap<Integer,Integer>();
            for(int i : nums){
                if(!count.containsKey(i)){
                    count.put(i,0);
                }
                count.put(i, count.get(i)+1);
            }
            
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            helper(res, count, new ArrayList<Integer>(), nums.length);
            return res;
        }
        
        private void helper(List<List<Integer>> res,HashMap<Integer, Integer> count,  List<Integer> list, int remain){
            //base case
            if(remain == 0){
                res.add(new ArrayList<Integer>(list));
                return;
            }
            
            for(Integer i : count.keySet()){
                int r = count.get(i);
                if(r>0){
                   count.put(i, r-1);
                   list.add(i);
                   helper(res, count, list, remain-1);
                   list.remove(list.size()-1);
                   count.put(i, r);
                }
            }
        }
    

    The runtime is 19ms, how could I improve it?


  • 0
    X

    @SSNico Do you get Ac? I use the similar method , but my solution is time exceeds .


  • 0
    X

    @xiaowu4 Oh, I see, I should use the hash.ketSet(), Thanks for your solution !!!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.