Subsets II

NeetCode: Subsets II · LeetCode: 90. Subsets II · Difficulty: Medium

Given an integer array nums that may contain duplicates, return all possible subsets without duplicate subsets, in any order.

Example

Text

Input:  nums = [1, 2, 2]    Output: [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
Input:  nums = [0]          Output: [[], [0]]

Brute force: all subsets, dedupe with a set

Generate all 2^n subsets with a bitmask as in Subsets, sort each one, and insert it into a TreeSet ordered by a list comparator. Subsets with the same values (for example the two ways of picking a single 2) collapse to one entry. Every duplicate is still generated and compared. A TreeSet iterates in comparator order, so the result is already sorted. (A HashSet<List<Integer>> would also remove duplicates, because List compares by content, but its iteration order is unspecified.)

LeetCode's Java signature returns List<List<Integer>>.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.TreeSet;

public class Main {
    static int cmp(List<Integer> a, List<Integer> b) {
        for (int i = 0; i < Math.min(a.size(), b.size()); i++) {
            int x = a.get(i), y = b.get(i);
            if (x != y) {
                return Integer.compare(x, y);
            }
        }
        return Integer.compare(a.size(), b.size());
    }

    static class Solution {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            int n = nums.length;
            TreeSet<List<Integer>> found = new TreeSet<>(Main::cmp);
            for (int mask = 0; mask < (1 << n); mask++) {
                List<Integer> subset = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    if ((mask >> i & 1) == 1) {
                        subset.add(nums[i]);
                    }
                }
                Collections.sort(subset);
                found.add(subset);
            }
            return new ArrayList<>(found);
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.subsetsWithDup(new int[] {1, 2, 2}));
        System.out.println(s.subsetsWithDup(new int[] {0}));
    }
}

Output

[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
[[], [0]]

Time: O(n · 2^n) to build plus O(n) per comparison inside the set, so up to O(n² · 2^n). Space: O(n · 2^n) for the set.

Optimal: sort and skip repeated values at the same level

Sort the array so equal numbers are adjacent, then loop over the next element to add: every node of the recursion is itself a subset (recorded on entry), and its children extend it with one more element from nums[start..].

To avoid duplicates, never pick the same value twice as the next element within one loop: if i > start && nums[i] == nums[i - 1], skip. Picking the second 2 right after the first 2 is still allowed one level deeper, where start has moved on, and that is how [2, 2] is produced.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static class Solution {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> result = new ArrayList<>();
            dfs(0, nums, new ArrayList<>(), result);
            return result;
        }

        private void dfs(int start, int[] nums, List<Integer> current, List<List<Integer>> result) {
            result.add(new ArrayList<>(current));
            for (int i = start; i < nums.length; i++) {
                if (i > start && nums[i] == nums[i - 1]) {
                    continue;
                }
                current.add(nums[i]);
                dfs(i + 1, nums, current, result);
                current.remove(current.size() - 1);
            }
        }
    }

    static int cmp(List<Integer> a, List<Integer> b) {
        for (int i = 0; i < Math.min(a.size(), b.size()); i++) {
            int x = a.get(i), y = b.get(i);
            if (x != y) {
                return Integer.compare(x, y);
            }
        }
        return Integer.compare(a.size(), b.size());
    }

    static List<List<Integer>> sorted(List<List<Integer>> lists) {
        List<List<Integer>> copy = new ArrayList<>(lists);
        copy.sort(Main::cmp);
        return copy;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(sorted(s.subsetsWithDup(new int[] {1, 2, 2})));
        System.out.println(sorted(s.subsetsWithDup(new int[] {0})));
    }
}

Output

[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
[[], [0]]

Time: O(n · 2^n) in the worst case (all values distinct); duplicates only reduce the work, since no duplicate subset is ever created. Space: O(n) recursion depth besides the output. The method sorts the caller's array in place.