Java 7 ms standard backtracking solution(simple)


  • 0
    T
    public class Solution {
        List<List<Integer>> ans = new LinkedList();
        LinkedList<Integer> comb = new LinkedList();
        public List<List<Integer>> permuteUnique(int[] nums) {
            HashMap<Integer,Integer> hm = new HashMap();
            for(int n : nums){
                if(hm.containsKey(n)){
                    hm.put(n,hm.get(n)+1);
                }   
                else {
                    hm.put(n,1);
                }
            }
            
            int count[] = new int[hm.size()];
            int ar[] = new int[hm.size()];
            int i=0;
            for(int k : hm.keySet()){
                ar[i] = k;
                count[i++] = hm.get(k);
            }
            
            backTrack(ar,count,nums.length);
            return ans;
        }
        private void backTrack(int[] nums,int[] count,int len){
            if(comb.size()>=len){
                LinkedList<Integer> temp = (LinkedList<Integer>) comb.clone();
                ans.add(temp);
                return;
            }
            for(int i =0;i<nums.length;i++){
                if(count[i]!=0){
                    comb.add(nums[i]);
                    count[i]--;
                    backTrack(nums,count,len);
                    count[i]++;
                    comb.remove(comb.size()-1);
                }
            }
            
        }
    }
    

Log in to reply
 

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