Coding Interview PatternsSubsets
MediumSubsets
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.
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: The power set of [1,2,3] contains 2³ = 8 subsets, including the empty set and the set itself.
Constraints
1 <= nums.length <= 10-10 <= nums[i] <= 10- All the numbers of
numsare unique
Approach
Subsets pattern
1. Sort the Input
- Sort
numsin ascending order to ensure subsets are generated in a consistent order - This makes it easy to avoid duplicates and produce sorted output
2. Backtracking Setup
- Initialize an empty
resultarray to collect all subsets - Define a recursive
backtrack(start, current)function starttracks which index to begin choosing fromcurrentholds the subset being built
3. Record Every Subset
- At the beginning of each recursive call, push a copy of
currentintoresult - This captures subsets of all sizes, including the empty set (when
currentis empty on the first call)
4. Explore Choices
- Loop from
starttonums.length - 1 - For each index
i, addnums[i]tocurrent - Recurse with
start = i + 1so each element is used at most once - After recursion, remove the last element (backtrack) to try the next choice
5. Return the Result
- After all recursive calls complete, sort the result lexicographically
- Return the complete list of subsets
Key Insight
- Each element has two choices: include it or exclude it, leading to 2^n total subsets
- By iterating from
startforward, we avoid revisiting earlier elements and naturally prevent duplicate subsets
Time
O(n * 2^n)there are 2^n subsets and copying each takes up to O(n)Space
O(n)recursion depth is at most n (excluding the output)Visualization
Input:
[1, 2, 3]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps