Subsets
Last Updated: April 1, 2026
Understanding the Problem
We need to generate every possible subset of the given array. A subset is any selection of elements (including none or all) from the array, where order does not matter. For an array of n elements, there are exactly 2^n subsets.
What makes this problem interesting is not just finding one subset, but systematically enumerating all of them without missing any and without producing duplicates. Think of it this way: for each element, you have a binary choice, include it or exclude it. That's n binary choices, giving 2^n total outcomes.
The key observation is that this "include or exclude" framing maps directly to both a recursive backtracking approach and a bitmask-based approach. Each gives us a clean way to explore every possible combination of choices.
Key Constraints:
1 <= nums.length <= 10→ With n at most 10, there are at most 2^10 = 1024 subsets. Any exponential approach is fine.-10 <= nums[i] <= 10→ Small value range, but all elements are unique, so we don't need to worry about deduplication.- All elements are unique → No duplicate handling needed, which simplifies the problem compared to Subsets II.
Approach 1: Iterative (Cascading)
Intuition
The simplest way to think about generating all subsets is to build them up one element at a time. Start with just the empty set. Then for each element in the array, look at every subset you've generated so far, make a copy of it with the new element added, and include that copy in your collection.
Here's why this works. When you process the first element, you take the empty set [] and create [1], giving you [[], [1]]. When you process the second element, you take each of those and add 2: [] becomes [2] and [1] becomes [1,2]. Now you have [[], [1], [2], [1,2]]. Each step doubles the number of subsets, which is exactly what we want since n elements produce 2^n subsets.
Algorithm
- Initialize the result with just the empty subset: [[]].
- For each number in the input array:
a. Look at every subset currently in the result.
b. Create a new subset by appending the current number to each existing subset.
c. Add all these new subsets to the result.
- Return the result.
Example Walkthrough
Code
- Time Complexity: O(n * 2^n). There are 2^n total subsets, and for each we spend up to O(n) time copying it.
- Space Complexity: O(n * 2^n). We store all 2^n subsets, each up to length n.
This approach is simple and correct, but involves a lot of list copying at each step. The backtracking approach builds subsets incrementally and only copies when a complete subset is recorded, making it the standard interview pattern for subset generation.
Approach 2: Backtracking
Intuition
Backtracking is the classic approach for this problem. It maps directly to the fundamental insight: for each element, you either include it or you don't. Picture a decision tree where at each level you decide about one element. Every node in this tree represents a valid subset, so we record it at every recursive call.
In practice, we iterate through the remaining elements starting from a given index. At each recursive call, we pick the next element to add, recurse, and then undo (backtrack) that choice. By always picking elements at index >= start, we ensure each subset is generated exactly once.
The backtracking approach works because it systematically explores every possible combination of include/exclude decisions. By always picking elements at index >= start, we never revisit earlier elements, which would create duplicates in different orders.
The "add to result at every call" trick is what makes this different from combinations or permutations: we don't wait for some base case to record a result. Every partial selection is itself a valid subset, from the empty set all the way up to the full array.
Algorithm
- Start with an empty current subset and index 0.
- Add a copy of the current subset to the result (every state is a valid subset).
- For each index i from the start index to the end of the array:
a. Add nums[i] to the current subset.
b. Recurse with start index = i + 1.
c. Remove nums[i] from the current subset (backtrack).
- The recursion naturally terminates when the start index exceeds the array bounds.
Example Walkthrough
Code
- Time Complexity: O(n * 2^n). We generate 2^n subsets, and each is copied into the result costing up to O(n) per copy.
- Space Complexity: O(n). The recursion stack goes at most n levels deep, and the current subset uses at most O(n) space. Output space is not counted as auxiliary.
Both the iterative and backtracking approaches have the same time complexity. But there is a completely different way to think about subset generation using bit manipulation, where each subset maps directly to a binary number.
Approach 3: Bit Manipulation
Intuition
Here is an elegant observation: for an array of n elements, there are 2^n subsets and also 2^n binary numbers from 0 to 2^n - 1. Each binary number of length n can represent a subset. If bit j is 1, element j is included. If bit j is 0, element j is excluded.
So we can generate all subsets by iterating from 0 to 2^n - 1 and, for each number, checking which bits are set to determine which elements belong in that subset. No recursion, no backtracking, just a direct mapping from integers to subsets.
Algorithm
- Calculate totalSubsets = 2^n (using bit shift: 1 << n).
- For each mask from 0 to totalSubsets - 1:
a. Create a new subset.
b. For each bit position j from 0 to n - 1: if bit j of mask is set, add nums[j] to the subset.
c. Add the subset to the result.
- Return the result.
Example Walkthrough
Code
- Time Complexity: O(n * 2^n). We iterate through 2^n masks, and for each mask we check n bits.
- Space Complexity: O(n * 2^n). We store all 2^n subsets, each with at most n elements. Auxiliary space is O(n) for the current subset.