Search code examples
javasubset

Using HashSet to filter duplicates does not work in subsets with duplicate problem

The problem is "Given a list of numbers that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order."

I have some simple code to use seemly similar ways to solve this problem. Howerver, Hashset approach does not work for some test cases such as [10, 10, 1, 2, 2, 2, 10]. But sort and neighbor integer comparison approach work.

It is just different from the permutation.

This code works:

import java.util.*; 

public class test {
    static ArrayList<ArrayList<Integer>> subsets_with_duplicate(ArrayList<Integer> numbers) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        Collections.sort(numbers);
        helper(res, new ArrayList<>(), numbers, 0);
        return res;
    }

    static void helper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> slate, ArrayList<Integer> numbers, int pos){
        int n=numbers.size();

        res.add(new ArrayList<Integer>(slate));
        //Set<Integer> set=new HashSet<>();
        for(int i=pos; i<n; i++){
            //if(!set.add(numbers.get(i)))
            if(i!=pos&&numbers.get(i).equals(numbers.get(i-1)))
                continue;
            slate.add(numbers.get(i));
            helper(res, slate, numbers, i+1);
            slate.remove(slate.size()-1);
        }
    }
    // Driver code
    public static void main(String args[])
    {
        ArrayList<Integer> arr= new ArrayList<>(Arrays.asList(10, 10, 1, 2, 2, 2, 10));
        for(var v:subsets_with_duplicate(arr)){
            System.out.println(v);
        }
    }
}

This code does not work -

import java.util.*; 

public class test {
    static ArrayList<ArrayList<Integer>> subsets_with_duplicate(ArrayList<Integer> numbers) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        //Collections.sort(numbers);
        helper(res, new ArrayList<>(), numbers, 0);
        return res;
    }

    static void helper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> slate, ArrayList<Integer> numbers, int pos){
        int n=numbers.size();

        res.add(new ArrayList<Integer>(slate));
        Set<Integer> set=new HashSet<>();
        for(int i=pos; i<n; i++){
            if(!set.add(numbers.get(i)))
            //if(i!=pos&&numbers.get(i).equals(numbers.get(i-1)))
                continue;
            slate.add(numbers.get(i));
            helper(res, slate, numbers, i+1);
            slate.remove(slate.size()-1);
        }
    }
    // Driver code
    public static void main(String args[])
    {
        ArrayList<Integer> arr= new ArrayList<>(Arrays.asList(10, 10, 1, 2, 2, 2, 10));
        for(var v:subsets_with_duplicate(arr)){
            System.out.println(v);
        }
    }
}

Why?

The partial output difference between these two solutions are highlighted in red.

enter image description here

Solution

  • You are missing Collections.sort(numbers); in your last program. If you uncomment then it will show the same result as earlier. Because without the HashSet code you are sorting data but not in the second program.

    static ArrayList<ArrayList<Integer>> subsets_with_duplicate(ArrayList<Integer> numbers) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    Collections.sort(numbers);
    helper(res, new ArrayList<>(), numbers, 0);
    return res;
}

static void helper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> slate, ArrayList<Integer> numbers,
        int pos) {
    int n = numbers.size();

    res.add(new ArrayList<>(slate));
    Set<Integer> set = new HashSet<>();
    for (int i = pos; i < n; i++) {
        if (!set.add(numbers.get(i))) {
            // if ((i != pos) && numbers.get(i).equals(numbers.get(i - 1))) {
            continue;
        }
        slate.add(numbers.get(i));
        helper(res, slate, numbers, i + 1);
        slate.remove(slate.size() - 1);
    }
}

// Driver code
public static void main(String args[]) {
    ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(10, 10, 1, 2, 2, 2, 10));
    for (var v : subsets_with_duplicate(arr)) {
        System.out.println(v);
    }
}