Watch 10 video solutions for Subsets, a medium level problem involving Array, Backtracking, Bit Manipulation. This walkthrough by NeetCode has 341,241 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0] Output: [[],[0]]
Constraints:
1 <= nums.length <= 10-10 <= nums[i] <= 10nums are unique.Problem Overview: Given an integer array nums, generate every possible subset (the power set). Each element can either be included or excluded, so the result contains 2^n subsets for an array of size n. The challenge is systematically exploring all combinations without duplicates.
Approach 1: Recursive Backtracking (Time: O(n * 2^n), Space: O(n))
This method builds subsets incrementally using backtracking. Start with an empty subset and recursively decide whether to include each element. At every recursion level, append the current subset to the result and iterate through remaining elements. Add an element, recurse deeper, then remove it (backtrack) to explore the next possibility. Because each element branches into two choices (include or skip), the algorithm generates 2^n subsets, and copying subsets contributes an additional O(n) factor.
Backtracking is easy to reason about and closely mirrors how humans think about combinations. You explicitly explore the decision tree: choose an element, continue building, then undo the choice. This approach generalizes well to many interview problems involving combinations, permutations, or constraint exploration.
Approach 2: Bit Manipulation (Time: O(n * 2^n), Space: O(1) auxiliary)
Every subset of an array can be represented by a binary mask. For an array of length n, numbers from 0 to (1 << n) - 1 represent all subset combinations. Each bit indicates whether an element is included: if the i-th bit is set, include nums[i] in the current subset. Iterate through all masks and check each bit using bit operations like mask & (1 << i). This approach leverages concepts from bit manipulation and avoids recursion entirely.
The insight is that the power set size is exactly 2^n, which matches the number of binary numbers with n bits. Each binary representation acts as a blueprint describing which elements belong to the subset. Iterating through masks guarantees every combination appears exactly once.
Recommended for interviews: Recursive backtracking is the most commonly expected solution. It demonstrates mastery of recursion, state exploration, and pruning patterns common in array combination problems. Bit manipulation is equally optimal in time complexity but is typically presented as an alternative or optimization mindset. Showing both approaches signals strong algorithmic flexibility.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking | O(n * 2^n) | O(n) recursion stack | Best for interviews and when learning subset generation patterns |
| Bit Manipulation | O(n * 2^n) | O(1) auxiliary | Useful when you want an iterative solution or are comfortable with bitmask enumeration |