/ Data Structure and Algorithms  

Leetcode 90. Subsets II

Question



Return all subsets of a set of integers (may contain duplicates).

Similar Questions

Solution

We can revise the solution of 78. Subsets. Let’s take a look at what would happen if we followed the idea of 78. Subsets directly. The previous idea was to add in first element, then add in second element to the subset formed previous. With n-th element, that is add n-th element to all previously formed subset

For example, the iteration process of nums[1, 2, 3].

1
2
3
4
initialize empty list:      []
1st iteration (nums[k] = 1):[[], [1]]
2nd iteration (nums[k] = 2):[[], [1], [2], [1, 2]]
3rd iteration (nums[k] = 3):[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

But what happens if there are duplicate numbers?

E.g, nums[1, 2, 2]

1
2
3
1st iteration (nums[k] = 1):[[], [1]]
2nd iteration (nums[k] = 2):[[], [1], [2], [1, 2]]
3rd iteration (nums[k] = 2):[[], [1], [2], [1, 2], [2], [1, 2], [2, 2], [1, 2, 2]]

We noticed that there are duplicate arrays.

How to avoid it? We can make a Hashset to store the results, everytime we have a new result, first sort the result, and try to add it to the set. This way we can avoid adding duplicates to the result set. Finally just need to convert the set to a list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// use set to avoid duplicate results
Set<List<Integer>> results = new HashSet<>();

// add empty list
results.add(new ArrayList<>());

for (int num : nums) {
    List<List<Integer>> temp = new ArrayList<>();

    for (List<Integer> existing : results) {
        List<Integer> newListAppend = new ArrayList<>(existing);
        newListAppend.add(num);

        // sort the result
        Collections.sort(newListAppend);

        temp.add(newListAppend);
    }

    // if duplicate result, then wouldn't add to set
    results.addAll(temp);
}

return new ArrayList<>(results);