Subsets II

1. Problem & Core Objective

Given an array that may contain duplicates, return all possible subsets. The result must not contain duplicate subsets.

nums = [1,2,2]
→ [[], [1], [1,2], [1,2,2], [2], [2,2]]      6 subsets, not 8

Constraints: 1 <= nums.length <= 10 · -10 <= nums[i] <= 10

What's actually being tested: deduplicating during the search rather than after it — and getting the skip condition exactly right. i > start versus i > 0 is a one-character difference that silently drops valid answers.

2. First-Principles Thought Process

Why [1,2,2] gives 6 and not 8

Question 1's template on [1,2,2] would produce all 2³ = 8 paths. But two pairs collide:

• choosing index 1 alone and choosing index 2 alone both give [2]
• choosing {0,1} and {0,2} both give [1,2]

The two 2s are interchangeable, so any subset using one of them has an identical twin using the other. Six distinct subsets remain.

The tempting fix, and why it's wrong

Collect all 8 and deduplicate with a Set. That works, but you have to canonicalise each subset first (sort it, or convert to a string), and you've still done the full 2^n work before throwing half away.

The better fix prunes the duplicate branch before descending into it — no wasted subtree, no post-filter.

Sort, then skip siblings

Sorting puts equal values adjacent. Then at any level, the loop sees the duplicates consecutively:

if (i > start && nums[i] == nums[i - 1]) continue;

Read it as: "if this is not the first choice at this level, and it repeats the previous value, skip it."

The first 2 at a level is allowed and explores its whole subtree. The second 2 at the same level would explore an identical subtree, so it's cut.

Why i > start and not i > 0

This is the crux. A repeated value is only redundant when it's a sibling — a second choice at the same depth. Deeper in a path, a repeat is legitimate: [2,2] needs both 2s.

i > start means "not the first iteration of this loop". At the top of a subtree, i == start, so the value is always allowed.

i > 0 would also fire when i == start (as long as start > 0), skipping the legitimate second 2 and losing [2,2] and [1,2,2] entirely.

Verified: on [1,2,2], the correct guard yields 6 subsets; i > 0 yields only 4.

3. Solution Paths

Approach 1 — Generate all subsets, deduplicate with a Set (brute force)

public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);                                  // canonical order within each subset
    Set<List<Integer>> seen = new LinkedHashSet<>();
    backtrack(nums, 0, new ArrayList<>(), seen);
    return new ArrayList<>(seen);
}

private void backtrack(int[] nums, int start, List<Integer> path, Set<List<Integer>> seen) {
    seen.add(new ArrayList<>(path));                    // Set drops the duplicates
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path, seen);
        path.remove(path.size() - 1);
    }
}

• Time O(n · 2^n) · Space O(n · 2^n)

Counter-questions on this approach

⭐ "Why does this need the sort, given the Set does the deduplication?"

Because List.equals is order-sensitive. Without sorting, [2,1] and [1,2] are different lists, so the Set wouldn't collapse them — and with duplicates in the input, the same multiset can be reached in different orders.

Sorting makes every generated subset non-decreasing, so equal multisets produce equal lists. The sort is load-bearing even here.

⭐ "It still explores all 2^n paths. How much is wasted?"

On [1,2,2] it builds 8 subsets and keeps 6. That's mild, but it compounds: with k copies of one value, the duplicate subtrees multiply, and an input like [2,2,2,2,2,2,2,2,2,2] explores 1024 paths to produce 11 subsets.

Pruning at the branch point avoids entering those subtrees at all, rather than exploring and discarding them.

"Is Set<List<Integer>> even a sound thing to do?"

It works because ArrayList implements equals and hashCode element-wise, so two lists with equal contents in the same order are equal. It's O(n) to hash each one, which adds a factor.

But it's fragile in spirit: correctness now depends on the sort producing canonical order. The pruned version has no such dependency — it simply never generates a duplicate.

Approach 2 — Sort and skip duplicate siblings (optimal)

public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);                                   // equal values become adjacent
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), result);
    return result;
}

private void backtrack(int[] nums, int start, List<Integer> path,
                       List<List<Integer>> result) {
    result.add(new ArrayList<>(path));                   // every node is a subset

    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue;   // skip duplicate SIBLINGS

        path.add(nums[i]);
        backtrack(nums, i + 1, path, result);
        path.remove(path.size() - 1);
    }
}

Trace — nums = [1,2,2] (already sorted):

Result: [], [1], [1,2], [1,2,2], [2], [2,2] — 6 subsets ✓

• Time O(n · 2^n) worst case (all distinct), far less with duplicates · Space O(n) depth

Counter-questions on this approach

⭐ "Walk me through i > start versus i > 0. Why does the difference matter?"

A repeated value is only redundant when it's a sibling — a second choice at the same depth, which would explore an identical subtree to the first choice.

i > start means "not the first iteration of this particular loop". When i == start I'm making the first choice at this level, so the value is always allowed — even if it equals the one before it in the array, because that one was chosen by an ancestor, not a sibling.

i > 0 doesn't distinguish those cases. At the call with start = 2 and path = [1,2], the loop's only iteration has i = 2; i > 0 is true and nums[2] == nums[1], so it would skip — and [1,2,2] is never generated.

I checked it: on [1,2,2] the correct guard produces 6 subsets, i > 0 produces 4, losing [1,2,2] and [2,2].

⭐ "Why is sorting required?"

Because the skip compares nums[i] with nums[i-1] — its immediate predecessor. That only detects duplicates if equal values are adjacent, which is exactly what sorting guarantees.

On unsorted [2,1,2] the two 2s are at indices 0 and 2, so nums[2] == nums[1] is 2 == 1, false — the duplicate slips through and [2] appears twice.

⭐ "Does this change the complexity, or just the constant?"

It genuinely reduces the number of nodes explored, though the worst case is unchanged: with all-distinct input nothing is ever skipped, so it's still O(n · 2^n).

The gain grows with duplication. With all n values identical there are only n + 1 distinct subsets, and the pruned search visits n + 1 nodes instead of 2^n. At n = 10 that's 11 versus 1024.

"Why record before the loop rather than at a leaf?"

Same reason as Subsets: every prefix is itself a valid subset. The skip affects which branches are taken, not where the answer is recorded.

"Could you dedupe by counting instead?"

Yes — group into (value, count) pairs and, for each distinct value, choose how many copies to take from 0 to count. That generates each distinct subset exactly once with no skip condition at all, and it's arguably cleaner. It's the standard approach for Combination Sum with heavy duplicates. Worth mentioning as an alternative framing.

Comparison

4. Why the Optimal Wins

Both correct approaches are O(n · 2^n) in the worst case, so this isn't primarily about complexity — it's about where the deduplication happens.

The Set version generates a duplicate subtree in full, then throws the results away, and its correctness depends on the sort producing canonical lists so List.equals collapses them.

The pruned version never enters the duplicate subtree. With heavy duplication the saving is dramatic — all-identical input goes from 2^n nodes to n + 1. And it has no hidden dependency on list equality.

The framing worth keeping:

Sort so duplicates are adjacent, then skip a repeat only when it's a SIBLING — i > start, not i > 0. A repeat deeper in the path is a legitimate second copy.

5. Java Prerequisites

The duplicate skip

Arrays.sort(nums);                                        // required — makes equals adjacent
if (i > start && nums[i] == nums[i - 1]) continue;        // i > start, NOT i > 0

Why the two guards differ

List.equals is order-sensitive — [1,2] does not equal [2,1]. That's why the Set approach needs the sort too.

Arrays.sort on int[] — dual-pivot quicksort, in place, O(n log n).

6. Interview Communication Guide

Clarifying questions: Can the input contain duplicates (yes — that's the whole problem)? Does subset order matter (no)? May I sort the input (yes — it's required)? Should [2,2] be included when the input has two 2s (yes — it's a distinct subset)?

The pitch

"The plain Subsets template would produce all 2^n paths, but with duplicates some of those are the same subset. On [1,2,2] the two 2s are interchangeable, so choosing either one alone gives [2] — 8 paths, 6 distinct subsets.

I could collect everything into a Set and deduplicate, but that explores the duplicate subtrees in full before discarding them. Better to prune before descending.

So: sort the array, which puts equal values adjacent, then at each level skip a value that repeats its predecessor — but only if it's a sibling:

if (i > start && nums[i] == nums[i-1]) continue;

The i > start is the part I'd be careful about. A repeat is only redundant when it's a second choice at the same depth, because that would explore an identical subtree. Deeper in a path a repeat is legitimate — [2,2] needs both.

Using i > 0 instead would also skip those legitimate repeats. On [1,2,2] it produces 4 subsets instead of 6, losing [2,2] and [1,2,2] — and it fails silently, just returning fewer answers.

Worst case is still O(n · 2^n) when everything is distinct, but with heavy duplication the saving is large: all-identical input has only n + 1 distinct subsets, and the pruned search visits n + 1 nodes rather than 2^n."

Edge cases to volunteer:

Name [2,2] and the unsorted input. The first is the minimal case where i > 0 breaks; the second is where forgetting the sort lets a duplicate through undetected.

7. Follow-Up Questions — Modified Constraints

⭐ "Do the same for Combination Sum with duplicates."

Question 5 — Combination Sum II. Identical skip condition, plus i + 1 instead of i because each element may be used only once, plus the sorted break when a candidate exceeds the remaining target. The sort serves all three purposes at once.

⭐ "Do the same for permutations with duplicates."

Permutations II, and the rule is different: if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;. There's no start index in permutations, so "sibling" is expressed as "the identical previous value hasn't been placed yet".

Worth noting the two rules aren't interchangeable, precisely because permutations scan the whole array at every level while subsets move forward.

"Deduplicate by counting instead of skipping."

Group the input into (value, count) pairs, then for each distinct value choose how many copies to take, 0 through count. Each distinct subset is generated exactly once with no skip condition. Cleaner to reason about, and it's the natural approach when duplication is heavy.

"What if values weren't comparable — arbitrary objects?"

Sorting requires an ordering. Without one, group by equals/hashCode into a map of counts and use the counting approach above. That's the general solution and it doesn't need Comparable at all.

"Return only the distinct subsets of size k."

Same skip, plus record only when path.size() == k, plus the prune if (path.size() + (n - i) < k) break;. Three independent conditions composing cleanly, which is a good sign the template is doing its job.

"What if n were 20 with all values distinct?"

2^20 is about a million subsets — still materialisable, but around 20 million integers of output. Beyond that you'd stream rather than accumulate. The skip gives no help when everything is distinct, so the only lever is not storing the results.