90. Subsets II

Given an integer array that may contain duplicates, return all possible subsets without duplicates in the result. Sort first so duplicate values are adjacent, then on the exclude branch skip repeated values at the same recursion depth with the guard i > start && nums[i] === nums[i-1].

● MediumBacktrackingSortingDuplicate SkippingTypeScript

PROBLEM What we're solving

Given nums = [1, 2, 2], return every unique subset (the power set, minus duplicates). Order inside subsets and between subsets does not matter. Expected output: [[], [1], [1,2], [1,2,2], [2], [2,2]] — six subsets, not eight. Without deduplication the two 2s would each produce an identical copy of [2] and [1,2].

KEY IDEA Sort + skip on the exclude branch

Insight → sort the array so equal values are adjacent, then inside the for-loop at each recursion level, if i > start && nums[i] === nums[i-1], skip nums[i]. This prunes the branch that would start a duplicate subset — identical first choices at the same depth produce identical subtrees, so we only keep the first.

RECIPE Sort, recurse, skip duplicates

0 · Sort. nums.sort() puts equal elements next to each other, making the duplicate-skip guard possible.
1 · Record every call. result.push([...current]) at the top of backtrack — every prefix of every path is a valid subset (including the empty set on the first call).
2 · Loop from start. For i = start to end: this avoids re-using elements before the current position and prevents subsets from appearing in multiple orders.
3 · Duplicate guard. If i > start (not the first choice at this depth) and nums[i] === nums[i-1], continue. The i > start part is crucial — it allows the first occurrence of a value to proceed normally.
4 · Include / recurse / exclude. Push, call backtrack(i + 1), pop. Classic backtracking template.

Classic confusion → the guard is i > start, not i > 0. Using i > 0 would wrongly skip the second 2 even when it's the first element chosen at a deeper level, eliminating valid subsets like [1,2,2].

COST Complexity & alternatives

Generate all, deduplicate with a Set

O(2ⁿ · n)

Builds duplicates then throws them away.

Sort + skip guard

O(2ⁿ · n)

Same worst-case bound but prunes duplicate subtrees early; smaller constant.

In the worst case (all unique elements) we still touch all 2ⁿ subsets. With many duplicates the tree is smaller: k distinct values means at most 2ᵏ unique subsets. Sorting costs O(n log n), which is dominated by the exponential enumeration. Each subset is copied in O(n) to result, giving the · n factor. Space is O(n) for the recursion stack (depth = n).

Pattern transfer → the same sort-and-skip trick works in Combination Sum II (LC 40 — pick k numbers that sum to target, no reuse), Permutations II (LC 47 — permutations with duplicates), and Palindrome Partitioningwhen combined with a used[] array. Whenever a backtracking problem says “may contain duplicates” and asks for unique results, sort first and add the skip guard.

RUN IT Sort, recurse, skip duplicate branches

nums =

step 0 / 19

STARTSorted input: [1, 2, 2]. We explore every include/exclude choice, recording each prefix as a subset.

1▶function subsetsWithDup(nums: number[]): number[][] {
2▶  nums.sort((a, b) => a - b);           // sort so duplicates are adjacent
3▶  const result: number[][] = [];
4▶  const current: number[] = [];
5 
6  function backtrack(start: number): void {
7    result.push([...current]);            // always record — every prefix is valid
8 
9    for (let i = start; i < nums.length; i++) {
10      // skip duplicate: same value as previous at this depth level
11      if (i > start && nums[i] === nums[i - 1]) continue;
12 
13      current.push(nums[i]);              // include nums[i]
14      backtrack(i + 1);                   // recurse with next index
15      current.pop();                      // exclude nums[i] (backtrack)
16    }
17  }
18 
19  backtrack(0);
20  return result;
21}

sorted nums102122

State

[1, 2, 2]

nums (sorted)

[]

current

start

—

depth

[]

result

subsets found

in current subsetelement being consideredskipped (duplicate guard)subset recorded

slowfast

TYPESCRIPT The solution, annotated

subsetsWithDup.ts
function subsetsWithDup(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);           // sort so duplicates are adjacent
  const result: number[][] = [];
  const current: number[] = [];

  function backtrack(start: number): void {
    result.push([...current]);            // always record — every prefix is valid

    for (let i = start; i < nums.length; i++) {
      // skip duplicate: same value as previous at this depth level
      if (i > start && nums[i] === nums[i - 1]) continue;

      current.push(nums[i]);              // include nums[i]
      backtrack(i + 1);                   // recurse with next index
      current.pop();                      // exclude nums[i] (backtrack)
    }
  }

  backtrack(0);
  return result;
}

Reading it block by block

Line 2 — sort first. Sorting makes equal elements adjacent, which is the prerequisite for the duplicate-skip guard. Without this step, equal values might be separated and the nums[i] === nums[i-1] check would miss some duplicates.

Lines 7–8 — record immediately. result.push([...current]) runs before the loop, so the empty set is captured on the very first call, and every intermediate prefix is captured on subsequent calls. The spread [...current] creates a snapshot; without it all entries would alias the same mutable array.

Lines 10–11 — the duplicate guard. i > startmeans we're past the first choice at this recursion level. Combined with nums[i] === nums[i-1], this says: “I already explored the subtree rooted at the previous copy of this value — skip this one.” The guard fires on the exclude path (when we loop back after popping), not on the include path.

Lines 13–15 — include / recurse / exclude. Classic backtracking: push the element, dive into backtrack(i + 1) (move forward so each element is used at most once per subset), then pop to undo and try the next candidate. Using i + 1 instead of start + 1 ensures we advance past the current position each time.

Complexity → O(2ⁿ · n) time — up to 2ⁿ subsets, each copied in O(n). O(n) auxiliary space for the recursion stack (depth = n) plus O(2ⁿ · n) for the output. Sorting adds O(n log n), dominated by the exponential term. With k distinct values, the tree has at most 2ᵏ leaves, so heavy duplicates shrink the real runtime significantly.

INTERVIEWFollow-ups they'll ask

“Return subsets in lexicographic order?” Already achieved by sorting nums first — iterating left-to-right naturally produces lexicographic order.
“Do it iteratively?” Start with [[]] and for each number extend existing subsets — but skip if the number equals the previous and the previous was just added in this round (track the range of newly added subsets).
“How does this change for Combination Sum II?” Add a target parameter, stop recursing when the running sum exceeds target, and only record when it equals target exactly — the same sort-and-skip guard handles duplicates identically.
“What if elements can be reused (LC 78 / 39)?” Drop the duplicate guard for LC 78 (all unique). For LC 39 change backtrack(i + 1) to backtrack(i) to allow re-picking the same element.
“Memory usage on very large inputs?” With n=20 the result can hold up to 2²⁰ ≈ 1 M subsets. A streaming / generator approach avoids materialising all subsets at once if only one is needed at a time.

OPTIMAL Backtracking

subsetsWithDup.ts
function subsetsWithDup(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);           // sort so duplicates are adjacent
  const result: number[][] = [];
  const current: number[] = [];

  function backtrack(start: number): void {
    result.push([...current]);            // always record — every prefix is valid

    for (let i = start; i < nums.length; i++) {
      // skip duplicate: same value as previous at this depth level
      if (i > start && nums[i] === nums[i - 1]) continue;

      current.push(nums[i]);              // include nums[i]
      backtrack(i + 1);                   // recurse with next index
      current.pop();                      // exclude nums[i] (backtrack)
    }
  }

  backtrack(0);
  return result;
}

ALT 1 Brute force — generate all subsets, then dedupe

O(2ⁿ · n) time · O(2ⁿ · n) space

Enumerate every one of the 2ⁿ subsets via bitmasks, sort each one so equal subsets share a canonical form, and drop repeats with a Set of string keys.

approach-2.ts
function subsetsWithDup(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);          // canonical element order
  const seen = new Set<string>();
  const result: number[][] = [];

  // Each bitmask 0..2^n-1 picks a subset of indices.
  for (let mask = 0; mask < (1 << nums.length); mask++) {
    const subset: number[] = [];
    for (let i = 0; i < nums.length; i++) {
      if (mask & (1 << i)) subset.push(nums[i]);
    }
    const key = subset.join(',');       // sorted nums => stable dedupe key
    if (!seen.has(key)) {
      seen.add(key);
      result.push(subset);
    }
  }
  return result;
}

Note → Correct, but it builds all 2ⁿ subsets even when duplicates make many of them identical, then pays for hashing every subset to filter them. Backtracking with the i > start && nums[i] === nums[i-1] skip never generates a duplicate in the first place.

MNEMONIC The one-liner

"Sort so twins stand side-by-side, then on the second twin at the same depth — skip."

TRIGGERS When you see _ → reach for _

"may contain duplicates" + "unique subsets"	sort + i > start skip guard
power set (all subsets)	backtrack recording every prefix
"no duplicate subsets" in combination/permutation problem	sort + skip-duplicate pattern
Combination Sum II / Permutations II	same sort-and-skip template

SKELETON The reusable shape

skeleton.ts
nums.sort((a, b) => a - b);
const result: number[][] = [];
const current: number[] = [];

function backtrack(start: number): void {
  result.push([...current]);
  for (let i = start; i < nums.length; i++) {
    if (i > start && nums[i] === nums[i - 1]) continue;
    current.push(nums[i]);
    backtrack(i + 1);
    current.pop();
  }
}

backtrack(0);
return result;

FLASHCARDS Tap to flip

Why sort before backtracking in Subsets II?

Sorting makes equal values adjacent so the guard nums[i] === nums[i-1] can detect and skip duplicate branches.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

For nums = [1, 2, 2], how many unique subsets does subsetsWithDup return?

QUESTION 02

Why must the array be sorted before backtracking?

QUESTION 03

The duplicate-skip condition is i > start && nums[i] === nums[i-1]. What happens if you write i > 0 instead of i > start?

QUESTION 04

Where is result.push([...current]) placed in the backtrack function?

QUESTION 05

What is the time complexity of subsetsWithDup?

QUESTION 06

Which change converts Subsets II into Combination Sum II (pick numbers summing to a target, no reuse)?

QUESTION 07

nums = [2, 2]. Which subsets does the algorithm produce?

QUESTION 08

#90 · Subsets IISort the array so duplicates are adjacent. On the "skip" branch of backtracking, skip all consecutive duplicates at the same depth (i > start && nums[i] == nums[i−1]) to avoid generating duplicate subsets.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Sort + skip on the exclude branch

RECIPE Sort, recurse, skip duplicates

COST Complexity & alternatives

RUN IT Sort, recurse, skip duplicate branches

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Backtracking

ALT 1 Brute force — generate all subsets, then dedupe

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _