Sharing 4ms java using backtracking with swap & set


  • 1
    S

    Using a swap the numbers and set to deal with the duplicated numbers.

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
    
        List<List<Integer>> result = new ArrayList<>();
        permuteUnique(nums, 0, result); 
        return result;     
    }
    
    private void permuteUnique(int[] nums, int idx, List<List<Integer>> result){
        if(nums.length == idx) {
            List<Integer> subResult = new ArrayList<>(); 
            for(int num: nums) subResult.add(num); 
            result.add(subResult); 
            return; 
        }
        
        Set<Integer> set = new HashSet<>();
        for(int pIdx=idx; pIdx<nums.length; pIdx++) { 
            // idx == pIdx then process them, otherwise skip the duplicated numbers.  
            if(idx != pIdx && (nums[idx] == nums[pIdx] || set.contains(nums[pIdx]))) continue; 
            
            set.add(nums[pIdx]);
    
            swap(nums, idx, pIdx);
            permuteUnique(nums, idx+1, result);
            swap(nums, pIdx, idx);
        }
    }
    
    private void swap(int[] nums, int idx1, int idx2){
        int num = nums[idx1];
        nums[idx1] = nums[idx2];
        nums[idx2] = num;
    }

Log in to reply
 

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