Coding Interview PatternsSubsets
MediumBacktracking
Subsets
Explanation & Solution
Description
Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Examples
Example 1
Input:nums = [1,2,3]
0
1
1
2
2
3
Output: [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
Explanation: There are 2³ = 8 subsets of a 3-element set.
Example 2
Input:nums = [0]
0
0
Output: [[],[0]]
Constraints
1 <= nums.length <= 10-10 <= nums[i] <= 10- All elements of
numsare unique
Approach
Backtracking pattern
1. Add Current State to Result
- At every call, push a copy of
currenttoresult— this captures subsets of all sizes, including the empty set
2. Iterate from Start Index
- Loop from
startto the end ofnums - The
startparameter ensures we only consider elements after the last chosen one, avoiding duplicate subsets
3. Include and Recurse
- Add
nums[i]tocurrentand recurse withi + 1as the new start - This explores all subsets that include
nums[i]
4. Backtrack
- After recursion, remove the last element with
pop() - This allows the next iteration to try a different element at this position
Key Insight
- Each element has two choices: include or exclude. The backtracking tree naturally generates all 2^n subsets by recording the state at every node, not just the leaves.
Time
O(n × 2^n)2^n subsets, each taking O(n) to copySpace
O(n) for the recursion stackVisualization
Input:
Backtracking Exploration
current path
empty
Press play to start
ExploringFoundBacktrack
22 steps