Difficulty: MediumBacktracking

Subsets II

Problem in Plain English

Given numbers that may repeat, return every unique subset from the empty set up to the full array. Subsets built from different twin positions count only once.

Problem Statement

Given an integer array nums that may contain duplicates, return every possible subset, including the empty set.

The answer must hold no duplicate subsets: two subsets built from different positions with equal values still count as one.

Return the subsets in any order.

Constraints

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

Examples

Example 1

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

There are two choices for the number of 1 values and three choices for the number of 2 values, giving six distinct subsets. The two positions containing 2 do not create two separate [2] answers, but both may be included in [2,2].

Example 2

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

At the minimum array length, either omit 0 to obtain the empty subset or keep it to obtain [0]. The value zero is an ordinary element; it does not mean an empty subset.

Example 3

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

Equal values need not be adjacent in the original input. Sorting brings the two 2 values together; keeping zero, one or two of them, with or without -1, gives six unique subsets. Negative numbers require numeric sorting in JavaScript.

Intuition

A subset chooses how many copies of each value to keep, rather than which equal-valued positions supplied them. In [1,2,2], choose zero or one 1 and zero, one or two 2 values: these choices give six subsets. A position-based search repeats [2] and [1,2]. We can remove those repeats afterward with canonical sorted keys, or sort once and allow only the first equal value to start a branch at each recursion level. Taking the next equal value deeper in that branch still permits [2,2].

Approaches

Enumerate and Dedup

Solution Details

Reveal Enumerate and Dedup: intuition, complexity, and code

Intuition

Enumerate all position choices and keep only the first occurrence of each sorted value sequence. A bit mask has one bit per input position: a set bit means include that element. Sorting each candidate makes equal multisets share one key, even on unsorted input. For [1,2,2], masks selecting either one of the two 2 positions both become [2], so a set retains one copy.

Step-by-Step Logic

For an array of length n, iterate every n-bit mask, including zero. Example 1 has eight masks; bit i selects nums[i], so bits are read from the right for positions 0, 1 and 2.
For each mask, scan every position and collect its selected values into a fresh list. Masks 001 and 010 in Example 1 produce [1] and [2] respectively.
Sort that list into a canonical value order and build an unambiguous key. Keep the list only if the key has not appeared before: mask 100 repeats [2], and mask 101 repeats [1,2].
Continue through all masks, including 110 for [2,2] and 111 for [1,2,2]. Return the six retained lists. Their order is allowed to differ from the displayed Example 1 output.

Why It Works

Every legal subset uses some selection of input positions, and its selection has a mask among all masks from zero through the largest n-bit mask. Therefore enumeration produces every required value multiset. Sorting removes irrelevant element order while preserving multiplicities. Two sorted sequences are equal exactly when their values and counts match; the delimiter-separated integer key (or Python tuple) identifies that sequence without collisions between different sequences. Adding a candidate only on its first key occurrence keeps every distinct subset exactly once. Mask zero contributes the empty subset.

Dry Run

Enumerate and Dedup: variable states at each step
Mask (bits 2,1,0)	Selected indices	Sorted candidate	Key status	Result after mask
`000`	`[]`	`[]`	new	`[[]]`
`001`	`[0]`	`[1]`	new	`[[],[1]]`
`010`	`[1]`	`[2]`	new	`[[],[1],[2]]`
`011`	`[0,1]`	`[1,2]`	new	`[[],[1],[2],[1,2]]`
`100`	`[2]`	`[2]`	already seen	unchanged
`101`	`[0,2]`	`[1,2]`	already seen	unchanged
`110`	`[1,2]`	`[2,2]`	new	`[[],[1],[2],[1,2],[2,2]]`
`111`	`[0,1,2]`	`[1,2,2]`	new	`[[],[1],[2],[1,2],[2,2],[1,2,2]]`; same six subsets as Example 1

Complexity Analysis

Time Complexity

O(n \log n \cdot 2^n)

Space Complexity

O(n \cdot 2^n)

Let n be the input length and U the number of unique subsets. Each of the 2^n masks scans n positions and sorts at most n selected elements, giving O(n log n · 2^n) worst-case time (expected set operations, with O(n)-length keys). The set retains O(nU) key storage, up to O(n · 2^n), even when returned output is excluded. One candidate and sorting workspace use O(n) transient space; returned lists add O(nU) worst-case storage. All-equal input has U = n + 1, but this method still scans every mask. Input is not mutated; n <= 10 makes the bit shifts safe in Java and JavaScript.

Code

Solution.java

1import java.util.ArrayList;2import java.util.Collections;3import java.util.HashSet;4import java.util.List;5import java.util.Set;6
7class Solution {8    public List<List<Integer>> subsetsWithDup(int[] nums) {9        List<List<Integer>> res = new ArrayList<>();10        Set<String> seen = new HashSet<>();11        int n = nums.length;12        for (int mask = 0; mask < (1 << n); mask++) {13            List<Integer> sub = new ArrayList<>();14            for (int i = 0; i < n; i++) {15                // Each bit represents a position, so equal values may recur.16                if ((mask & (1 << i)) != 0) sub.add(nums[i]);17            }18            // Sorting only the candidate preserves input and canonicalizes order.19            Collections.sort(sub);20            if (seen.add(sub.toString())) res.add(sub);21        }22        return res;23    }24}

Hints

Hint 1

Imagine independently including or excluding each position. Where do [1,2,2] masks produce the same values?

Hint 2

Sorting puts equal values next to each other. Starting two sibling branches with the same value would repeat every extension of that prefix.

Hint 3

Use the guard i > start when comparing a candidate with its predecessor. Record a copy of every path on entry, then recurse at i + 1 and undo the append.

Edge Cases

All values equal, such as [2,2,2], give exactly four subsets: [], [2], [2,2], [2,2,2]. Multiplicity must be preserved.
An array with no duplicates has all $2^n$ subsets; ten distinct values produce 1024 answers and exercise the maximum output bound.
A single [0] yields [[],[0]]; the empty subset and a subset containing zero are different.
Unsorted duplicates and negative values, such as [2,-1,2], require canonical ordering before using the adjacent-duplicate rule. All snippets preserve the original input order.
Returned subsets own independent lists: editing one answer must not change another answer or the input.

Common Mistakes and Interview Tips

Skipping every equal neighbor with i > 0 instead of i > start removes valid multiple-copy subsets such as [2,2].
Converting nums to a set erases multiplicity; two copies of 2 are allowed in a subset even though duplicate subsets are forbidden.
Appending the mutable path itself instead of copying it makes all DFS answers share storage and change during backtracking.
Recursing with start equal to i reuses an input position; recurse at i + 1 and remove the appended value after returning.
JavaScript default sort compares strings. Use a numeric comparator, especially for negative numbers; sort a copy when preserving input.
Interview tip: distinguish auxiliary space from answer storage, and explain why skipping only equal siblings preserves every possible count of each repeated value.

Key Takeaway

When equal-valued positions represent the same output choice, sort and suppress duplicate sibling branches. Preserve repeated values along deeper branches, snapshot each answer, and undo each temporary choice before exploring another sibling.