How do you solve Subsets?

Implement a depth-first search (DFS) that at each step decides whether to include nums[i] in the current subset. When the index reaches the length of nums, append a copy of the current subset to the results. Backtracking by popping the last element after exploring the include branch ensures the state is restored for the exclude branch. This yields all subsets in O(n * 2^n) time and space.

Subsets

Q: What is the time complexity of Subsets?

O(n * 2^n). There are 2^n subsets, and each subset takes O(n) time to copy into the result list. The recursion explores all branches of the binary decision tree.

Q: What pattern does Subsets use?

The Pattern: Backtracking (State Restoration) The Heuristic: For problems requiring all combinations or subsets, use a recursive 'choose, explore, un-choose' pattern where each decision point branches on including or excluding the current element, and state is restored after exploring each branch to enable exhaustive search without duplication.

Medium Backtracking

Problem

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. You may return the solution in any order.

1 ≤ nums.length ≤ 10
−10 ≤ nums[i] ≤ 10
All elements of nums are unique.

Example

Input: nums = [1,2,3]

Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

The algorithm explores the decision tree of including or excluding each element. Starting at index 0 with an empty subset, it chooses to include 1, then recursively explores subsets including 2 and 3, building subsets like [1,2,3]. It backtracks by removing elements and explores alternative branches, such as excluding 1 and including 2 and 3, generating [2,3]. This exhaustive exploration ensures all 2^n subsets are generated without duplicates.

Approach

Straightforward Solution

A brute-force approach enumerates all subsets by iterating over all binary masks from 0 to 2^n - 1, which is feasible but less intuitive and less flexible for extensions.

Core Observation

Each element in nums can either be included or excluded from a subset, leading to a binary decision tree with 2^n leaves representing all subsets.

Path to Optimal

Preview

The key insight is to use backtracking to recursively explore the decision space: at each index, choose to include the current element and recurse, then backtrack and choose to exclude it and recurse…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Implement a depth-first search (DFS) that at each step decides whether to include nums[i] in the current subset. When the index reaches the length of nums, append a copy of the current subset to the results…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n * 2^n)

There are 2^n subsets, and each subset takes O(n) time to copy into the result list. The recursion explores all branches of the binary decision tree.

Space

O(n)

The recursion stack and the temporary subset list use O(n) space, where n is the length of nums. The output list uses O(n * 2^n) space but is not counted as auxiliary space.

Pattern Spotlight

Backtracking (State Restoration)

For problems requiring all combinations or subsets, use a recursive 'choose, explore, un-choose' pattern where each decision point branches on including or excluding the current element, and state is restored after exploring each branch to enable exhaustive search without duplication.

Solution

Python

1class Solution:
  def subsets(self, nums: list[int]) -> list[list[int]]:
      res = []
      subset = []
5
      def dfs(i):
          if i >= len(nums):
              res.append(subset.copy())
              return
          
          subset.append(nums[i])
          dfs(i + 1)
          
          subset.pop()
          dfs(i + 1)
16
      dfs(0)
      return res

Step-by-Step Solution

Initialize Result and Temporary Subset Containers

3res = []
4subset = []

Objective

To prepare storage for accumulating all subsets and the current subset being constructed.

Key Insight

The result list collects all subsets found during recursion, while the temporary subset list represents the current path in the decision tree. Keeping these separate allows efficient backtracking and final output construction.

Interview Quick-Check

Core Logic

The result list stores all subsets, and the temporary subset list tracks the current combination being explored.

State & Boundaries

The temporary subset is modified in-place during recursion and must be copied when adding to results to avoid mutation issues.

Recursively Explore Inclusion and Exclusion of Each Element

To systematically generate all subsets by deciding at each index whether to include or exclude the current element.

Start Recursive Exploration and Return All Subsets

To initiate the recursive process from the first element and return the complete list of subsets after exploration.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 14 Critical

subset.pop()

Remove the last element to backtrack and restore state.

Popping the last element is critical to undo the previous choice, ensuring the subset list is correct for exploring the exclusion branch.

Line 8 Critical

res.append(subset.copy())

Add a copy of the current subset to the results list.

Copying is essential because the subset list is mutable and will be modified during backtracking; storing a copy preserves the current state.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why is it necessary to 'un-choose' (pop) the last element after the recursive call that includes it?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Subsets from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Subsets drill

or drill a free problem

1	`class Solution:`
2	`def subsets(self, nums: list[int]) -> list[list[int]]:`
3	`res = []`
4	`subset = []`
5
6	`def dfs(i):`
7	`if i >= len(nums):`
8	`res.append(subset.copy())`
9	`return`
10
11	`subset.append(nums[i])`
12	`dfs(i + 1)`
13
14	`subset.pop()`
15	`dfs(i + 1)`
16
17	`dfs(0)`
18	`return res`