Small modification of Permutation I , using a set


  • 10
    Q
    public static List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        permute(nums,0,nums.length,res);
        return res;
    }
    public static void permute(int[] nums, int i, int j, List<List<Integer>> res){
        
        if(i == j-1){
            ArrayList<Integer> list = new ArrayList<Integer>();
            for(int x:nums) list.add(x);
            res.add(list);
            return;
        }
        HashSet<Integer> visited= new HashSet<Integer>();
        for(int k=i;k<j;k++){
            if(!visited.contains(nums[k])){
                swap(nums,i,k);
                permute(nums,i+1,j,res);
                swap(nums,i,k);
                visited.add(nums[k]);
            }
            
        }
    }
    public static void swap(int[] nums, int i,int j){
        int tmp = nums[j];
        nums[j] = nums[i];
        nums[i] = tmp;
    }

  • 1
    S

    Since you are using a HashSet to check for duplicates, you don't need to sort the input array.
    Also, since HashSet.add() returns true when the value does not exist already, you can replace

    if(!visited.contains(nums[k])){
        ...
        visited.add(nums[k]);
    }
    

    with

    if(visited.add(nums[k])){
        ...
    }

Log in to reply
 

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