Sharing 4ms java using backtracking with swap & set

  • 1

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

    public List<List<Integer>> permuteUnique(int[] 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); 
        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; 
            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.