Comparing neighboring integer does not work in Permute Array of Integers Duplicates Allowed

Question

Given an array of numbers with possible duplicates, return all of its permutations in any order.

It works when I use a HashSet to skip duplicates.

    package test;

import java.util.*; 

public class test {
      static ArrayList<ArrayList<Integer>> get_permutations(ArrayList<Integer> arr) {
            ArrayList<ArrayList<Integer>> res=new ArrayList<>();
            //Collections.sort(arr);
            helper(arr, 0, res);
            return res;
        }
        
        static void helper(ArrayList<Integer> arr, int pos, ArrayList<ArrayList<Integer>> res){
            int n=arr.size();
            if(pos>=n){
                res.add(new ArrayList<Integer>(arr));
                return;
            }
            
            Set<Integer> set=new HashSet<>();
            for(int i=pos; i<n; i++){
                //if(i>pos&&arr.get(i).equals(arr.get(i-1)))  
                if(!set.add(arr.get(i)))
                    continue;
                
                Collections.swap(arr, pos, i);
                helper(arr, pos+1, res);
                Collections.swap(arr, pos, i);
            }
        }
    // Driver code
    public static void main(String args[])
    {
        ArrayList<Integer> arr= new ArrayList<>(Arrays.asList(3,3,8,8,9,9,9));
        for(var v:get_permutations(arr)){
            System.out.println(v);
        }
    }
}

However, if I sorted the array and skipped the duplicates by comparing neighboring integer, it does not work for some test cases such as [3,3,8,8,9,9,9].

    import java.util.*; 
    
    public class test {
          static ArrayList<ArrayList<Integer>> get_permutations(ArrayList<Integer> arr) {
                ArrayList<ArrayList<Integer>> res=new ArrayList<>();
                Collections.sort(arr);
                helper(arr, 0, res);
                return res;
            }
            
        static void helper(ArrayList<Integer> arr, int pos, ArrayList<ArrayList<Integer>> res){
            int n=arr.size();
            if(pos>=n){
                res.add(new ArrayList<Integer>(arr));
                return;
            }
            
            //Set<Integer> set=new HashSet<>();
            for(int i=pos; i<n; i++){
                if(i>pos&&arr.get(i).equals(arr.get(i-1)))  
                //if(!set.add(arr.get(i)))
                    continue;
                
                Collections.swap(arr, pos, i);
                helper(arr, pos+1, res);
                Collections.swap(arr, pos, i);
            }
        }
    // Driver code
    public static void main(String args[])
    {
        ArrayList<Integer> arr= new ArrayList<>(Arrays.asList(3,3,8,8,9,9,9));
        for(var v:get_permutations(arr)){
            System.out.println(v);
        }
    }
}

This is opposite to subset solution.

The outputs highlighted in red part are the problem.

What did I miss here?

Answer 1

My Coach in Interview Kickstart helped me found out the problem in my code. His/Her finding is "In the if condition of for loop, You have written if(i>pos&&arr.get(i).equals(arr.get(i-1))) but it should be if (i != pos && (arr.get(i) == arr.get(pos) || (i > 0 && arr.get(i) == arr.get(i-1)))) to handle the duplicate elements correctly."

I have converted the fix to what I can understand better -

if (i > pos && (arr.get(i) == arr.get(pos) || arr.get(i) == arr.get(i-1)))

Earlier I missed the case arr.get(i) == arr.get(pos).

The correct solution is

    import java.util.*; 
    
    public class test {
          static ArrayList<ArrayList<Integer>> get_permutations(ArrayList<Integer> arr) {
                ArrayList<ArrayList<Integer>> res=new ArrayList<>();
                Collections.sort(arr);
                helper(arr, 0, res);
                return res;
            }
            
        static void helper(ArrayList<Integer> arr, int pos, ArrayList<ArrayList<Integer>> res){
            int n=arr.size();
            if(pos>=n){
                res.add(new ArrayList<Integer>(arr));
                return;
            }
            
            for(int i=pos; i<n; i++){
                if (i > pos && (arr.get(i) == arr.get(pos) || arr.get(i) == arr.get(i-1)))
                    continue;
                
                Collections.swap(arr, pos, i);
                helper(arr, pos+1, res);
                Collections.swap(arr, pos, i);
            }
        }
    // Driver code
    public static void main(String args[])
    {
        ArrayList<Integer> arr= new ArrayList<>(Arrays.asList(3,3,8,8,9,9,9));
        for(var v:get_permutations(arr)){
            System.out.println(v);
        }
    }
}