Subsets
The key idea
Each element is independently either in or out of a subset, so the power set has
2^n members. A depth-first walk over an index makes a binary include/exclude decision at every position; recording the running subset at each node of that decision tree yields every subset exactly once.Problem
Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. You may return the answer in any order.
Constraints
1 <= nums.length <= 10-10 <= nums[i] <= 10- All the numbers of
numsare unique.
Examples
Input: nums = [1,2,3]
Output: [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
Input: nums = [0]
Output: [[],[0]]
Complexity
Time: O(n * 2^n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Backtracking problems
- Combination SumMEDIUM
- Combination Sum IIMEDIUM
- Combination Sum IIIMEDIUM
- CombinationsMEDIUM
- Generate ParenthesesMEDIUM
- Letter Combinations of a Phone NumberMEDIUM
- Matchsticks to SquareMEDIUM
- N-QueensHARD
- N-Queens IIHARD
- Non-decreasing SubsequencesMEDIUM
- Palindrome PartitioningMEDIUM
- Partition to K Equal Sum SubsetsMEDIUM