Skip to content

Volume ITechnology

4.18.1 — Subsets ​

LeetCode 78 · Medium · ★ Blind 75

The problem ​

Return every possible subset of the array. All values are distinct. Any order is fine.

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

n is at most 10, so there are at most 2^{10} = 1024 subsets.

The pattern ​

Each element is independently in or out. Two choices per element, n elements, so 2^n subsets. That count is the first thing to say — it tells you an exponential answer is expected and correct.

Think of this like packing a suitcase for a trip. For every single item you own, you make a strict binary choice: "Does this go in the suitcase, or does it stay at home?" If you have 3 items, you make 3 binary decisions, leading to 2 \times 2 \times 2 = 8 possible different suitcases you could pack.

Draw the tree before writing anything:

                      []
              take 1 /  \ skip 1
                  [1]      []
           take 2 / \      / \ skip 2
              [1,2] [1]  [2]  []
              /  \  / \  / \  / \
        [1,2,3][1,2][1,3][1][2,3][2][3][]

Eight leaves, and the leaves are the answers. Every path from the root to a leaf is one decision per element.

Solution 1 — include or exclude ​

The tree written directly as code.

python
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []  # (1)
        path = []  # (2)

        def backtrack(i: int):  # (3)
            if i == len(nums):  # (4)
                result.append(path[:])       # (5) copy — not path itself
                return

            path.append(nums[i])             # (6) branch 1: take it
            backtrack(i + 1)  # (7)
            path.pop()                       # (8) undo

            backtrack(i + 1)                 # (9) branch 2: skip it

        backtrack(0)  # (10)
        return result
ts
function subsets(nums: number[]): number[][] {
  const result: number[][] = [];  // (1)
  const path: number[] = [];  // (2)

  function backtrack(i: number): void {  // (3)
    if (i === nums.length) {  // (4)
      result.push([...path]);  // (5)
      return;
    }
    path.push(nums[i]);  // (6)
    backtrack(i + 1);  // (7)
    path.pop();  // (8)

    backtrack(i + 1);  // (9)
  }

  backtrack(0);  // (10)
  return result;
}

Line by line ​

(1) result collects every finished subset.

(2) path is the subset being built right now. One list is shared by the whole search. Items are added before going deeper and removed on the way back, which is the backtracking pattern from 4.8.4.

(3) backtrack(i) decides about element i. Everything before i has already been decided, and path holds the ones that were taken.

(4) Every element has been decided, so path is one complete subset. This is a leaf of the tree drawn above.

(5) Save a copy of it. path[:] makes a new list with the same items. See the note below for why the copy matters.

(6) Branch one: take element i.

(7) Decide about the rest, with element i included.

(8) Undo the take. path is back to how it was before line (6).

(9) Branch two: skip element i, and decide about the rest without it.

(10) Start with element 0.

path[:] is a copy. Appending path itself stores a reference to the one list that keeps changing, so at the end every entry in result would be the same empty list. This bug produces plausible-looking output that is entirely wrong, and it catches everyone once.

The path.pop() is the undo, restoring the state so the skip branch starts clean.

There is no constraint here — every subset is valid, so nothing is pruned. That is why this is the simplest problem in the chapter: it has three of the four parts and no pruning at all.

Solution 2 — the start-index loop ​

The same answers from a different tree shape, and this is the version that generalises to every other problem in the chapter.

python
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        path = []

        def backtrack(start: int):
            result.append(path[:])           # EVERY node is an answer
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i + 1)             # i + 1: never reuse or look back
                path.pop()

        backtrack(0)
        return result
ts
function subsets(nums: number[]): number[][] {
  const result: number[][] = [];
  const path: number[] = [];

  function backtrack(start: number): void {
    result.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1);
      path.pop();
    }
  }

  backtrack(0);
  return result;
}

Two things make this version worth learning even though the first one is easier to picture.

Every node is recorded, not just the leaves. A subset is complete at every point in the walk — there is no "unfinished" subset. That is why the result.append sits at the top with no base case. Compare this with permutations, where only full-length paths count.

backtrack(i + 1) means never look back. Starting the loop at start and recursing with i + 1 guarantees each element is considered once and in increasing index order, so [1,2] is generated and [2,1] never is. That is exactly what you want when order does not matter.

Changing that single i + 1 to i allows reuse, and gives you 4.18.2 Combination Sum. One character.

Solution 3 — iterative, no recursion at all ​

Start with the empty subset. For each element, add a copy of every existing subset with that element appended.

python
def subsets(self, nums):
    result = [[]]
    for n in nums:
        result += [subset + [n] for subset in result]
    return result

[1,2,3] builds up as:

[[]]
[[], [1]]
[[], [1], [2], [1,2]]
[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

The size doubles with each element, which is the 2^n made visible.

Solution 4 — bitmasks ​

Each subset corresponds to an n-bit number: bit i set means element i is included.

python
def subsets(self, nums):
    n = len(nums)
    result = []
    for mask in range(1 << n):                    # 0 to 2^n − 1
        result.append([nums[i] for i in range(n) if mask & (1 << i)])
    return result

1 << n is 2^n. mask & (1 << i) tests bit i.

Seeing a subset as one integer is the same idea as bitmask dynamic programming, where a subset of up to about 20 items is stored as one integer and used as a DP state (4.29). Meeting it here makes that technique much less mysterious later.

Complexity ​

O(2^n \times n) time. There are 2^n subsets and copying each costs up to O(n).

O(n) space for the recursion and the path, not counting the output.

Let's derive this:

  • Time Complexity: There are 2^n possible subsets (the leaves of our recursive tree, or total nodes in the loop approach). For each subset, we make a full copy of the path array. The maximum length of the path is n. So making 2^n copies, each taking up to n time, gives O(n \cdot 2^n) overall time.
  • Space Complexity: The recursive call stack goes as deep as the number of elements, n. The temporary path array also holds at most n elements. Thus, auxiliary space is O(n).

You cannot do better, because the output itself has 2^n entries. Say this — it reframes the exponential from a failing into a requirement.

Edge cases ​

  • One element, like [5]. Two subsets: [] and [5].
  • The empty subset is always included. It is the leaf where every element was skipped.
  • Negative numbers. They change nothing. Subsets do not care about values, only about which positions are in or out.

Where this goes next ​

  • Subsets II — duplicates in the input. Sort, then skip equal siblings. 4.18.4.
  • Combinations (LeetCode 77) — subsets of exactly size k. The same loop with a length check in the base case.
  • Combination Sum — the same loop with reuse allowed. 4.18.2.
  • Partition Equal Subset Sum — asks whether some subset hits a target. Enumerating all 2^n is too slow, and DP gets there in O(n \times \text{sum}). 4.23. That contrast is worth holding on to: enumerate when you need every answer, use DP when you only need to know whether one exists.

What the interviewer will push on ​

"How many subsets are there?" 2^n. Say it before you write code.

"Why do you copy the path?" Because it is one shared mutable list.

"Why is every node an answer in the loop version?" A subset is complete at every stage; there is nothing to finish.

"What changes if the array has duplicates?" Sort and skip equal siblings.

"Can you do it without recursion?" The doubling loop, or bitmasks.

One thing to volunteer: draw the tree for [1,2,3] before coding. It takes fifteen seconds and it makes every later problem in this chapter a variation you can see rather than guess.

Next: 4.18.2 Combination Sum — the same loop with one character changed, and the first real pruning.

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