Sweaty Imposter

Subsets II

MediumSubsets (BFS-style generation)NeetCode 150MidOpen on LeetCodeUpdated

You're given an integer array nums that may contain duplicates. Return every possible subset of nums, with no two subsets containing the same multiset of values. Include the empty subset. The subsets, and the values inside each one, may be returned in any order.

Examples

nums = [3,1,3] returns [[],[1],[1,3],[1,3,3],[3],[3,3]]

Picking the first 3 or the second 3 gives the same subset, so [3] and [1,3] each appear once.

nums = [0] returns [[],[0]]

One value gives two subsets: with it and without it.

nums = [4,4,4] returns [[],[4],[4,4],[4,4,4]]

With all values equal, a subset is just a choice of how many 4s to take.

Constraints

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

Hints

Hint 1

If you run the usual Subsets algorithm, where do duplicate subsets come from?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Sort nums so equal values sit together, then backtrack. Every call records the current subset, then tries each index i from start onward as the next value to add. Skip i when i > start and nums[i] == nums[i - 1]: at a given depth, choosing the second copy of a value would rebuild the subsets the first copy already produced. The first copy still gets to be followed by the second one deeper in the recursion, which is how [3,3] appears. O(n * 2^n) time in the worst case, O(n) extra space besides the output.

Time

O(n * 2^n)

Space

O(n)

Pitfall

Skipping duplicates with i > 0 instead of i > start. That also blocks taking a second copy deeper in the recursion, so [3,3] and [4,4,4] never appear.

Solutions

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

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