Subsets II LeetCode 90 — Skip Duplicates

LeetCode 90 — Subsets II — gives you an integer array nums that may contain duplicates and asks you to return all possible subsets (the power set). The result must not contain duplicate subsets, and the order of the subsets in the output does not matter. Unlike Subsets I (LeetCode 78), the input array is not guaranteed to have distinct elements, which means naive backtracking will generate the same subset multiple times from different paths through the decision tree.

For example, given nums = [1, 2, 2], the expected output is [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]. There are two copies of 2 in the input, but subsets like [2] and [1, 2] should each appear only once in the result — not twice for each copy of 2. A brute-force approach that generates all 2^n subsets and deduplicates afterward is both wasteful and hard to implement cleanly.

The efficient solution builds on the Subsets I backtracking template and adds a single skip condition. Sorting the array first brings duplicates together, enabling a simple loop-level check to prune entire duplicate subtrees before they are explored.

Subsets I (LeetCode 78) guarantees that all elements in nums are distinct. The standard backtracking solution starts from a given index, records the current path as a valid subset at every node (not just leaf nodes), then iterates from that index forward — appending each element, recursing with start + 1, and popping afterward. Because all elements are distinct, each unique combination of indices produces a unique subset.

Subsets II breaks that assumption. When nums contains two copies of 2, the backtracking tree has two branches at any given level where you could "pick the first 2" or "pick the second 2." Both branches lead to identical subsets downstream. Without intervention the output contains [2] twice, [1, 2] twice, and so on — one copy generated from each duplicate element.

The fix does not require a visited set or post-processing deduplication. A single condition inserted into the inner loop — skip when nums[i] equals nums[i-1] and i is not the first choice at this level — eliminates all duplicate branches before they are explored. This keeps the algorithm O(n * 2^n) in the worst case, the same as Subsets I.

After sorting nums, the skip condition is: inside the backtracking loop, if i > start AND nums[i] == nums[i-1], skip this iteration with continue. The i > start check ensures we are not at the very first element of the current level — the first element is always valid regardless of its value. The nums[i] == nums[i-1] check detects that this element has the same value as the previous one at this level, meaning its subtree will produce an identical set of subsets.

Concretely, for nums = [1, 2, 2] (sorted) and a backtracking call with start = 1: the loop considers i = 1 (value 2) and i = 2 (value 2). When i = 2, i > start (2 > 1) is true and nums[2] == nums[1] (2 == 2) is true, so we skip i = 2 entirely. This prevents the subtree rooted at "pick the second 2 at level start=1" from being explored, eliminating all duplicates it would have generated.

The condition works at every recursive level simultaneously. Each recursive call sets its own start parameter, and the skip check is relative to that local start. Duplicates are pruned at the exact level where they would first diverge into identical paths, cutting the tree efficiently without over-pruning valid paths.

The skip condition deliberately uses i > start rather than i > 0. At any recursive call, start is the index of the first element available for selection at this level. When i equals start, we are considering the very first choice at this level and must always allow it — even if its value happens to equal the element just before it in the sorted array (which was selected at an outer level, not the current one).

Using i > 0 instead of i > start would incorrectly skip valid subsets. For nums = [1, 2, 2], consider the recursive call with start = 2 reached via the path [1]. Here i starts at 2. If we used i > 0, we would check nums[2] == nums[1] which is 2 == 2 — true — and skip i = 2 entirely. But i == start, so this is the only element available at this level. Skipping it would omit the valid subset [1, 2, 2] from the output.

The distinction is subtle but critical. The i > start guard says "only skip if this is not the first choice at this level." Combined with nums[i] == nums[i-1], it means: "skip only if a previous branch at this same level already explored this value." First-choice elements at any level are always valid and must never be skipped by the duplicate condition.

Trace through nums = [1, 2, 2] (sorted). Without the skip condition, the backtracking tree generates subsets: [], [1], [1, 2] (first 2), [1, 2, 2], [1, 2] (second 2), [2] (first 2), [2, 2], [2] (second 2). This produces [1, 2] twice and [2] twice — four duplicates in a result of 8 subsets when only 6 are unique.

With the skip condition applied, the tree is pruned: at level start=0, i=0 picks 1 (ok, first choice), i=1 picks first 2 (ok, first choice at this level), i=2 would pick second 2 but 2>0 AND nums[2]==nums[1] — SKIP. At level start=1 (inside path=[1]), i=1 picks first 2 (ok), i=2 would pick second 2 but 2>1 AND nums[2]==nums[1] — SKIP. The pruned tree generates exactly: [], [1], [1,2], [1,2,2], [2], [2,2] — the correct 6 unique subsets.

The key observation from the trace is that skipping happens at every level independently. The condition fires at start=0 to prevent a second [2] root branch and fires again at start=1 to prevent a second [1,2] branch. Each application removes an entire subtree worth of duplicates with a single continue statement.

In Python, sort nums first. The subsetsWithDup function initializes an empty results list and calls backtrack(0, []). The backtrack(start, path) function appends path[:] to results immediately (every node is a valid subset), then loops i from start to len(nums) - 1. Inside the loop: if i > start and nums[i] == nums[i-1], continue. Append nums[i] to path, recurse with backtrack(i+1, path), then pop. Time complexity is O(n * 2^n) — up to 2^n subsets each taking O(n) to copy. Space complexity is O(n) for the recursion stack depth.

In Java, Arrays.sort(nums) first. The public List<List<Integer>> subsetsWithDup(int[] nums) method initializes a List<List<Integer>> result and calls backtrack(nums, 0, new ArrayList<>(), result). The private void backtrack method adds new ArrayList<>(current) to result immediately, then loops i from start to nums.length - 1. Inside the loop: if i > start && nums[i] == nums[i-1], continue. Add nums[i] to current, recurse with i+1, then remove the last element. The structure is identical to Python — only syntax differs.

Both implementations record the current path at the start of each recursive call, not only at leaf nodes. This is the defining feature of subset generation versus combination generation: in combinations you record only when the path meets a length or sum target, but in subsets every intermediate node is already a valid output. The sort + skip pattern is the only addition needed to handle duplicates.

Combination Sum (LeetCode 39) and Combination Sum II (LeetCode 40) use similar backtracking templates. Combination Sum II also requires skipping duplicates using the same i > start AND nums[i] == nums[i-1] condition — the only differences are that Combination Sum II passes start + 1 (no reuse) and records only paths that reach the exact target rather than every intermediate node. Understanding Subsets II makes Combination Sum II feel like a straightforward adaptation.

Permutations II (LeetCode 47) is the permutation analog of Subsets II: given an array with possible duplicates, generate all unique permutations. It uses a different deduplication technique — a used-boolean array plus a sort — because permutations visit all positions rather than progressing forward through the array. The underlying idea (sort first, skip when the current value equals the previous unused value) echoes the same duplicate-pruning philosophy.

N-Queens (LeetCode 51) and Palindrome Partitioning (LeetCode 131) extend the backtracking framework with domain-specific validity checks. The core pattern — make a choice, recurse, undo the choice, skip invalid branches early — is identical. Mastering Subsets II gives you a clean mental model for the skip-duplicate pattern that recurs across the entire backtracking family of problems on LeetCode.