Subsets
Asked at Amazon, Oracle
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
| Oracle | Medium | View all Oracle 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.
Visual walkthrough for nums = [1,2,3]:
Decision tree (binary — include or skip):
[]
/ \ [1] [] / \ /
[1,2] [1] [2] [] / \ / \ / \ /
[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] [] All 8 subsets: [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]`
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.
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Subsets?
Subsets is asked at Amazon, Oracle. 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.