78. Subsets
Asked at Amazon, Oracle, Bloomberg, TikTok
Difficulty
Medium
Time
O(n * 2^n)
Space
O(n)
Pattern
Array
Companies
4
Problem
You are given an array nums of distinct integers. Return all possible subsets of nums — this collection is also called the power set.
A subset is any selection of elements from nums, taken in any order. The empty selection counts as a subset, and so does the full array. Because the input has no duplicates, no two subsets will look the same, so you never need to remove repeats.
The answer may be returned in any order — the judge only checks which subsets you produced, not their sequence.
A good way to think about it: walk through the elements one by one. For each element you make a binary choice — include it in the current subset or skip it. Every full sequence of choices gives one subset, so with n elements you get 2^n subsets in total.
Every element is in or out
Constraints
- ●
1 <= nums.length <= 10 - ●
-10 <= nums[i] <= 10 - ●
All the numbers of nums are unique.
Examples
nums = [1,2,3][[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]nums = [0][[],[0]]Asked At
4 companies| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
| Oracle | Medium | View all Oracle questions → |
| Bloomberg | Medium | View all Bloomberg questions → |
| TikTok | Medium | View all TikTok questions → |
How to Think About It
Backtracking approach: at each element, make a choice: include it or skip it. Recursively explore both branches. When you reach the end of the array, the current subset is one valid result. The recursion tree has 2^n leaves, one for each subset.
Bit manipulation approach: for n elements, there are 2^n subsets. Each subset maps to a binary number from 0 to 2^n - 1. If bit i is set, include nums[i]. For n=3: 000={}, 001={3}, 010={2}, 011={2,3}, 100={1}, 101={1,3}, 110={1,2}, 111={1,2,3}.
Comparing approaches: backtracking is more flexible (easy to add pruning for constraints), while bit manipulation is more compact but harder to extend. Interviewers often prefer backtracking for clarity.
Complexity: both approaches produce O(2^n) subsets. Each subset takes O(n) to copy. Total time O(n * 2^n). Space is O(n) for recursion depth (backtracking) or O(1) extra (bit manipulation).
Optimal Approach
Backtracking: maintain a current subset and an index. At each step, add the current subset to the result (it is always valid). Then for each remaining element starting from index, include it, recurse, and backtrack (remove it). This explores all inclusion/exclusion decisions.
Walkthrough with nums = [1,2]:
- Start: subset=[], index=0
- Add [] to result. Try include 1: subset=[1], index=1
- Add [1] to result. Try include 2: subset=[1,2], index=2
- Add [1,2] to result. Backtrack: subset=[1]
- Backtrack: subset=[]
- Try include 2: subset=[2], index=1
- Add [2] to result. Backtrack: subset=[]
- Result: [[], [1], [1,2], [2]]
Time: O(n * 2^n). Space: O(n) recursion depth.
Backtracking: add, recurse, undo
What Trips People Up in Real Interviews
Forgetting the empty set. The power set always includes []. If your backtracking starts by adding the current subset before exploring children, you get it naturally.
Off-by-one in bit manipulation. The loop must run from 0 to (1 << n) - 1 inclusive. If you use < instead of <=, you miss the last subset (the full set).
Modifying the subset array in-place without copying. In backtracking, after adding to result, you must pop before returning. For the result, append a copy (subset[:]), not a reference.
Assuming subsets must be sorted in the result. The problem says order does not matter, but if you want a consistent order, sort the input first.
Trying to avoid the 2^n output by pruning. You cannot — the problem requires ALL subsets. There is no way to reduce the output size below 2^n.
Solution Code
O(n * 2^n) timedef subsets(nums):
result = []
def backtrack(start, current):
result.append(current[:])
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
return resultFrequently Asked Questions
What is the Subsets problem?
Given a set of distinct integers, return all possible subsets (the power set). This is a classic backtracking problem that tests your understanding of recursion, inclusion/exclusion decisions, and generating combinations.
How do you solve Subsets?
The optimal approach runs in O(n * 2^n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Subsets?
Subsets is asked at Amazon, Oracle, Bloomberg, TikTok. It is a medium difficulty problem.
What are common mistakes on Subsets?
- Forgetting the empty set. The power set always includes []. If your backtracking starts by adding the current subset before exploring children, you get it naturally.
- Off-by-one in bit manipulation. The loop must run from 0 to (1 << n) - 1 inclusive. If you use < instead of <=, you miss the last subset (the full set).
- Modifying the subset array in-place without copying. In backtracking, after adding to result, you must pop before returning. For the result, append a copy (subset[:]), not a reference.
- Assuming subsets must be sorted in the result. The problem says order does not matter, but if you want a consistent order, sort the input first.
- Trying to avoid the 2^n output by pruning. You cannot — the problem requires ALL subsets. There is no way to reduce the output size below 2^n.