Skip to content

Volume ITechnology

4.18.4 — Subsets II ​

LeetCode 90 · Medium

The problem ​

Return all unique subsets. The input may contain repeated values.

[1,2,2]  →  [[], [1], [1,2], [1,2,2], [2], [2,2]]

[2] appears once even though there are two 2s to choose from, and [1,2] appears once even though it could be formed with either 2.

The pattern ​

4.18.1 unchanged, plus one guard. The guard is the most-missed detail in this chapter, so we derive it rather than memorise it.

Where the duplicates come from ​

Draw the tree for [1,2,2] using the start-index loop, and mark the two 2s as 2ₐ and 2ᵦ:

                        []
           /            |            \
        [1]           [2ₐ]          [2ᵦ]        ← level 1
        / \             |
    [1,2ₐ] [1,2ᵦ]    [2ₐ,2ᵦ]                    ← level 2
       |
   [1,2ₐ,2ᵦ]

Two collisions, and they have the same cause. At level 1, choosing 2ₐ and choosing 2ᵦ produce the identical subset [2], and the whole subtree beneath them is identical too. Same at level 2 with [1,2ₐ] and [1,2ᵦ].

Think of having two absolutely identical red Lego bricks in a pile. If I ask you to build a tower with one red brick, it doesn't matter which of the two identical red bricks you grab first—the tower looks exactly the same. If you try to build a tower starting with Brick A, and then later try to build a "new" tower starting with Brick B, you're just wasting time building the exact same shape twice.

The duplicates are always siblings — different choices made at the same position in the tree. They are never along a path, because along a path you are building a longer subset, and [2ₐ, 2ᵦ] is legitimately [2,2].

So the rule is: at each level, use each distinct value only once.

The guard ​

Sort the array first so that equal values are adjacent, then:

python
if i > start and nums[i] == nums[i - 1]:
    continue

i > start, not i > 0. This is the entire subtlety.

  • i == start is the first choice at this level. It must always be allowed, even if it equals the previous value in the array — because at this level the previous value was chosen by the parent, not by a sibling.
  • i > start means a sibling earlier in this loop already tried this value, so trying it again produces a duplicate subtree.

Write i > 0 instead and [2,2] disappears, because the second 2 gets skipped even when the first 2 is its parent rather than its sibling.

Trace [1,2,2] with each version once. It takes a minute and it fixes this rule permanently.

The solution ​

python
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()                                  # (1) equal values must be adjacent
        result = []
        path = []

        def backtrack(start: int):  # (2)
            result.append(path[:])  # (3)

            for i in range(start, len(nums)):  # (4)
                if i > start and nums[i] == nums[i - 1]:  # (5)
                    continue                         # a sibling already used this value

                path.append(nums[i])  # (6)
                backtrack(i + 1)  # (7)
                path.pop()  # (8)

        backtrack(0)
        return result
ts
function subsetsWithDup(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);  // (1)
  const result: number[][] = [];
  const path: number[] = [];

  function backtrack(start: number): void {  // (2)
    result.push([...path]);  // (3)

    for (let i = start; i < nums.length; i++) {  // (4)
      if (i > start && nums[i] === nums[i - 1]) continue;  // (5)

      path.push(nums[i]);  // (6)
      backtrack(i + 1);  // (7)
      path.pop();  // (8)
    }
  }

  backtrack(0);
  return result;
}

Line by line ​

(1) Sort, so equal values sit next to each other. The guard in line (5) compares each value with its left neighbour, so it only works on a sorted list.

(2) backtrack(start) extends the current subset using elements from position start onward, exactly as in solution 2 of 4.18.1.

(3) Every point in the search is a valid subset, so save a copy straight away.

(4) Try each element from start onward as the next one to add.

(5) Skip a value that a sibling already tried. If this value equals the one just before it, and that earlier one was also an option in this same loop (i > start), then adding this one would build exactly the same subsets again. So skip it. When i == start, it is the first option in this loop, so it is always allowed, even if it equals the value before it. That earlier value was chosen by the parent, not by a sibling.

(6) Add the element,

(7) extend the subset using only later positions, and

(8) undo, ready for the next option.

Sorting is mandatory, not a convenience. The guard compares nums[i] with nums[i-1], which only finds duplicates if equal values sit next to each other. Skip the sort on [2,1,2] and the duplicates survive.

Everything else is 4.18.1: every node is an answer, i + 1 means no reuse, and the path is copied when recorded.

Trace ​

[1,2,2] sorted stays [1,2,2].

At start = 0: record []. Loop i = 0, 1, 2.

  • i = 0 (value 1): i == start, allowed. Path [1], recurse from 1.
    • record [1]. Loop i = 1, 2.
    • i = 1 (value 2): i == start (start is 1), allowed. Path [1,2], recurse from 2 → record [1,2], then [1,2,2].
    • i = 2 (value 2): i > start and equals nums[1] → skipped. This is what stops the second [1,2].
  • i = 1 (value 2): i > start (start is 0) but nums[1] != nums[0], allowed. Path [2], recurse from 2 → record [2], then [2,2].
  • i = 2 (value 2): i > start and equals nums[1] → skipped. This stops the second [2].

Six unique subsets. ✓

Edge cases ​

  • All values equal, like [2, 2, 2]. The answer is [], [2], [2, 2], [2, 2, 2]: one subset per possible count of 2s.
  • No repeats. The guard never fires, and the code behaves exactly like Subsets.
  • Forgetting to sort, as in [2, 1, 2]. The two 2s are not neighbours, so the guard misses them, and [1, 2] appears twice.

The alternative: deduplicate afterwards ​

You could generate everything and filter:

python
seen = set(tuple(s) for s in all_subsets)

It works and it is easy. It also builds the entire duplicated search tree first, which for heavily repeated input can be exponentially larger than the answer. On [2]*10 it explores 1,024 paths to produce 11 subsets.

Pruning at the source is the point of the exercise, and saying why the filter approach is worse is a better answer than either one alone.

Complexity ​

O(2^n \times n) in the worst case, when every value is distinct and nothing is pruned. With duplicates it is proportional to the number of unique subsets, which is exactly what the guard buys.

O(n) space beyond the output.

Let's break this down:

  • Time Complexity: Sorting takes O(n \log n). Without duplicates, generating subsets is O(n \cdot 2^n). With duplicates, the time is strictly proportional to the number of unique subsets because the guard perfectly prunes duplicate branches. In the worst case (all unique elements), it remains O(n \cdot 2^n).
  • Space Complexity: The sorting might take O(n) or O(\log n) space depending on the language. The recursive call stack depth is at most n, and the path array takes up to n space. Total auxiliary space is O(n).

Where this goes next ​

The same guard, unchanged, appears in:

  • Combination Sum II — 4.18.5.
  • 3Sum — the duplicate skips in 4.5.3 are the same idea in a loop rather than a recursion.
  • Permutations II — a different guard, not used[i-1], because permutations have no start index and the sibling relationship is expressed differently. Compare the two conditions side by side; understanding why they differ is worth more than memorising either.

What the interviewer will push on ​

"Why must you sort first?" The guard compares adjacent elements.

"Why i > start and not i > 0?" The first choice at each level must always be allowed; only siblings are duplicates. Give the [2,2] example.

"Could you just deduplicate at the end?" Yes, and explain why it can be exponentially more work.

"How does this differ from the guard in Permutations II?" No start index there, so the sibling test becomes not used[i-1].

One thing to volunteer: say "duplicates come from siblings, never from ancestors" before writing the guard. That sentence is the derivation, and it makes the i > start obvious rather than magical.

Next: 4.18.5 Combination Sum II — this guard and the no-reuse rule working together.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet