Subsets II: the one skip condition that changes everything

LeetCode 78 (Subsets) is clean — every element is unique, so every distinct selection of indices produces a distinct subset. LeetCode 90 breaks that assumption. The input can have duplicates, and the output must not. That single change from "may contain duplicates" is small in words and surprisingly deep in implementation.

The naive path is obvious: generate everything, then deduplicate. It works, it is simple, and it produces exactly the wrong habit for the rest of the backtracking series. The better solution is to never generate the duplicates in the first place. One skip condition — i > start and nums[i] == nums[i-1] — does the entire job. Let me show why it is correct, why i > 0 is wrong, and what to do with it in production.

The problem

Given an integer array nums that may contain duplicates, return all possible subsets (the power set) with no duplicate subsets in the result. Full statement: LeetCode 90.

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

What the constraints actually force

1 <= nums.length <= 10 and -10 <= nums[i] <= 10. Same size as Subsets (78), same value range.

n = 10 means 2^10 = 1024 possible subsets in the no-duplicate case. Add duplicates and the actual distinct-subset count shrinks, but the search space stays 2^n. At O(n * 2^n) you are doing at most 10 * 1024 = 10,240 operations — nothing to optimize for performance. The constraint is giving you permission to use any algorithm that is correct.

The constraint that matters here is the duplicate tolerance combined with the uniqueness requirement on output. The problem does not say the input is sorted. You need to sort it yourself. Once sorted, equal elements are adjacent, which is the structural fact that makes the skip condition possible. Without sorting, you would need a hash set to detect duplicates across arbitrary positions — more expensive and harder to reason about.

The value range [-10, 10] is small enough that you could technically use frequency arrays to enumerate subsets, but that does not generalize. Ignore it.

Approach 1: generate everything, then deduplicate

Sort the array, enumerate all 2^n subsets using bit manipulation, serialize each subset to a hashable key, and drop duplicates with a set.

class Solution:
    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        n = len(nums)
        seen = set()
        result = []
 
        for mask in range(1 << n):
            subset = []
            for j in range(n):
                if mask & (1 << j):
                    subset.append(nums[j])
            key = tuple(subset)
            if key not in seen:
                seen.add(key)
                result.append(subset)
 
        return result

using System;
using System.Collections.Generic;
using System.Linq;
 
public class Solution {
    public IList<IList<int>> SubsetsWithDup(int[] nums) {
        Array.Sort(nums);
        int n = nums.Length;
        var seen = new HashSet<string>();
        var result = new List<IList<int>>();
 
        for (int mask = 0; mask < (1 << n); mask++) {
            var subset = new List<int>();
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0)
                    subset.Add(nums[j]);
            }
            string key = string.Join(",", subset);
            if (seen.Add(key)) {
                result.Add(subset);
            }
        }
 
        return result;
    }
}

The C# version uses HashSet<string> with comma-joined values as the key. This works because after sorting, equal subsets will always produce the same string. The seen.Add(key) call returns true only if the element was not already present — so the if (seen.Add(key)) guard is a neat way to check-and-insert in one call.

Time: O(n * 2^n) — iterating 2^n masks, each taking O(n) to build and serialize.

Space: O(n * 2^n) — the hash set stores up to 2^n keys, each of length O(n). The duplication overhead is real: if the input is [2, 2, 2], you generate 8 subsets from the bitmask loop but only 4 are distinct. You create and hash 8 strings to keep 4. When duplicates are dense the wasted work grows.

Approach 2: backtracking that never generates the duplicates

Sort, then backtrack. At each recursive level, before picking element i, check whether nums[i] == nums[i-1] and i > start. If both are true, skip i — the branch rooted at nums[i] at this level is structurally identical to the branch already explored with nums[i-1].

class Solution:
    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        result = []
 
        def backtrack(start: int, current: list[int]) -> None:
            result.append(current[:])
 
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue
                current.append(nums[i])
                backtrack(i + 1, current)
                current.pop()
 
        backtrack(0, [])
        return result

using System;
using System.Collections.Generic;
 
public class Solution {
    public IList<IList<int>> SubsetsWithDup(int[] nums) {
        Array.Sort(nums);
        var result = new List<IList<int>>();
 
        void Backtrack(int start, List<int> current) {
            result.Add(new List<int>(current));
 
            for (int i = start; i < nums.Length; i++) {
                if (i > start && nums[i] == nums[i - 1])
                    continue;
                current.Add(nums[i]);
                Backtrack(i + 1, current);
                current.RemoveAt(current.Count - 1);
            }
        }
 
        Backtrack(0, new List<int>());
        return result;
    }
}

Time: O(n * 2^n) in the worst case (no duplicates). Each leaf of the recursion tree is a distinct subset, copying it costs O(n). With duplicates the tree shrinks, but the bound does not change because it is defined by the worst-case input.

Space: O(n) for the recursion call stack and the current list, not counting the output. The maximum call depth is n. Approach 1 holds all subsets in the hash set simultaneously; Approach 2 only holds the path from root to the current node.

Hand trace through nums = [1, 2, 2]

After sorting: [1, 2, 2]. Let me step through the backtracking tree. At each call, the format is backtrack(start, current).

Reading off the recorded subsets in order: [], [1], [1,2], [1,2,2], [2], [2,2]. Six subsets. That matches the expected output.

The critical skip fires twice. At the root level (start=0), when the loop reaches i=2, nums[2]=2 == nums[1]=2 and i=2 > start=0 — skip. At the [1] level (start=1), when the loop reaches i=2, nums[2]=2 == nums[1]=2 and i=2 > start=1 — skip. Both skip correctly because we already explored the branch that starts with nums[i-1] at this level.

Why i > start and not i > 0

This is the question that trips people up. The condition i > 0 and nums[i] == nums[i-1] would skip element i any time it equals the previous element in the sorted array — even when it is the first element being considered at this recursion level. That would incorrectly prune valid subsets.

Concrete case: nums = [1, 2, 2], call backtrack(1, [1]). Now start = 1. The loop starts at i = 1, so nums[1] = 2 is the first element tried at this level. With i > 0 you would check nums[1] == nums[0], which is 2 == 1 — false, so no skip here. But now call backtrack(1, []) (from the root). At start = 0, the loop starts at i = 0. Then i = 1: with i > 0, you check nums[1] == nums[0] which is 2 == 1 — still false. Now consider nums = [2, 2] and you are at the root call backtrack(0, []). At i = 1: i > 0 is true, nums[1] == nums[0] is 2 == 2 — you would skip it. But i = 1 == start = 0 is false, so i > start would NOT skip. That is correct — at the root level, you are deciding "should I start a branch with the second 2?" The answer is no (that branch would duplicate the branch starting with the first 2). With i > 0 it would also skip here, which is... actually correct in this specific case. Let me be more precise.

The real case where i > 0 breaks things: nums = [1, 2, 2], call backtrack(2, [1, 2]). Here start = 2. The loop starts at i = 2. i > 0 is true, nums[2] == nums[1] is 2 == 2 — SKIP. But i == start, so i > start is false — do NOT skip. The subset [1, 2, 2] gets generated correctly. Without i > start, you would lose [1, 2, 2] from the output.

The rule: skip only when the current element would produce a duplicate branch at the same recursion level, meaning a sibling branch. A duplicate sibling occurs when nums[i] == nums[i-1] and i != start (i.e., i > start). The i > start check is exactly "are we past the first element at this level."

Edge cases

Single element (nums = [5]): backtrack(0, []) records [], picks 5, calls backtrack(1, [5]) which records [5] and has no more elements. Output: [[], [5]]. Correct.

All identical (nums = [2, 2, 2]): after sorting, the first pick is nums[0] = 2. At each subsequent level, i > start prevents the second occurrence of 2 from starting a new branch at the same level. The tree produces [], [2], [2,2], [2,2,2] — four subsets, which is the correct power set for a multiset {2,2,2}. The brute force approach would generate 8 bitmask combinations and deduplicate to 4.

Already sorted (nums = [1, 2, 3]): no duplicates, so the skip condition never fires. The behavior degenerates to plain Subsets (78). Sorting a sorted array costs O(n log n) but that is dominated by the O(n * 2^n) backtracking.

Negatives (nums = [-1, -1, 0]): sorting puts -1, -1, 0 in order. The skip fires for the second -1 at the root level. Output includes [], [-1], [-1,-1], [-1,-1,0], [-1,0], [0]. Negative values are handled identically to positives — the value comparison is exact.

Empty-ish: the constraint says nums.length >= 1, so you cannot receive an empty array. The initial result.append([]) in the backtracking version handles n = 1 correctly without any special case.

Which version to ship

Approach 2, always. The hash set approach (Approach 1) is useful to have in your head as a "I can always deduplicate at the end" fallback, but it has real costs: it allocates O(n * 2^n) space for string keys, it serializes every subset even the ones that will be discarded, and it doesn't compose cleanly into the rest of the backtracking family. The moment you encounter Combination Sum II (40) or Permutations II (47), you will use the same skip condition — and if you learned only the hash set approach here, you will have to re-derive it from scratch.

Approach 2 also has a cleaner invariant you can reason about: after the sort, the recursion tree is exactly the tree of distinct subsets, no more. You are not paying to generate extras and throw them away.

The O(n) space for the call stack versus O(n * 2^n) for the hash set is not a hypothetical difference — at n = 10 and dense duplicates like [1,1,1,1,1,1,1,1,1,1], the brute force builds 1024 string keys to keep 11 subsets. Approach 2 builds and records exactly 11.

Comparison

Both hit the same time class. The space difference is the reason to prefer Approach 2, and the generalizability difference is the stronger reason.

The transferable pattern and where to go next

The underlying pattern is level-wise duplicate pruning on a sorted input during backtracking. Sorting clusters equal elements. At each recursion level, you allow the first occurrence of each value and skip subsequent ones (i > start and nums[i] == nums[i-1]). This prevents duplicate subtrees from being explored. The key structural insight: two branches at the same level that both start with the same value will produce identical subtrees, so exploring only the first one is sufficient and complete.

This pattern appears in at least three other problems in the series:

Combination Sum II (40) — find all unique combinations that sum to a target, from an input with possible duplicates. Exact same skip condition, exact same sort-first requirement. The only change from Subsets II is that you stop recursing when the running sum exceeds the target instead of collecting every prefix. If you are comfortable here, go there next.

Permutations II (47) — all unique permutations of a possibly-duplicate input. The skip logic is similar but the structure is different: you cannot use a start index (permutations allow all positions), so you typically use a used[] boolean array and skip nums[i] == nums[i-1] and not used[i-1]. The same "equal sibling at the same level -> skip" idea, implemented differently because permutations don't have a fixed start position.

Subsets (78) — the problem that precedes this one in the series. No duplicates, no skip needed. If Subsets II feels shaky, go back to 78 first and make sure the backtracking template is solid before adding the skip condition.

Combination Sum III (216) — pick k numbers from 1-9 that sum to n. No duplicates in the input, but the constraint on count k adds a new pruning condition. A good problem for practicing constraint-based pruning after the duplicate case is clear.

Subsets II sits at position 6 in the backtracking series — after the pure-subset and combination-sum problems, before problems that require more elaborate state. It is the problem that makes the duplicate-skipping pattern explicit and gives it a clean home. Once you can explain exactly why i > start and not i > 0, the rest of the duplicate-backtracking problems become variations.