Subsets
On this page
Problem statement
Given a list of distinct integers, return all of its subsets (the power set). Each subset is a list of some of the numbers, including the empty subset and the full list. The result must not contain the same subset twice, and subsets and their contents may be in any order.
The entry point to backtracking. Interviewers use it to see whether you can write a clean choose / explore / undo loop and explain why it never produces duplicates. Original problem: LeetCode 78.
Example
![For nums = [1, 2, 3] there are 8 subsets: [], [1], [2], [3], [1, 2], [1, 3], [2, 3] and [1, 2, 3]. Each number is either in or out, so 2 × 2 × 2 = 8.](https://storage.ghost.io/c/cc/3d/cc3dd2ec-1125-4515-87dd-11389c0d3c50/content/images/2026/11/000-6085f513.png)
Input: nums = [1, 2, 3]
Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]] # any order
Input: nums = [0]
Output: [[], [0]]
Constraints (assumed)
- 1 ≤ n ≤ 10.
- −10 ≤ nums[i] ≤ 10, all distinct.
What this question tests
- Writing the backtracking template (choose, explore, undo) without bugs.
- Avoiding duplicate subsets by only moving forward through the list.
- Knowing the output size (2ⁿ) and why no algorithm can beat O(n · 2ⁿ).
Questions to ask first
- Are the numbers distinct? (Yes. With duplicates, see Subsets II below.)
- Does the order of subsets, or of numbers inside a subset, matter? (No.)
- Should the empty subset be included? (Yes.)
- How large can n be? The output doubles with each number, so n is always small; n = 30 would already be a billion subsets.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.