Subsets
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.
The challenge is enumerating all of them without missing any and without producing duplicates. For each element, there is a binary choice: include it or exclude it. That gives n independent binary choices, and 2^n total outcomes.
This "include or exclude" framing maps directly to a recursive backtracking approach and to a bitmask-based approach. Each enumerates every combination of choices exactly once.
Key Constraints:
1 <= nums.length <= 10→ With n at most 10, there are at most 2^10 = 1024 subsets, so an exponential enumeration runs comfortably.-10 <= nums[i] <= 10→ Values are small and fit in any integer type, with no overflow concern.- All elements are unique → No deduplication is needed, so any subset built from distinct index choices is automatically distinct.
Approach 1: Iterative (Cascading)
Intuition
Build the subsets up one element at a time. Start with only the empty set. For each element in the array, take every subset generated so far, make a copy with the new element added, and add that copy to the collection.
When the first element is processed, the empty set [] produces [1], giving [[], [1]]. When the second element is processed, each of those gets a copy with 2 added: [] produces [2] and [1] produces [1,2], giving [[], [1], [2], [1,2]]. Each pass doubles the count, so after processing all n elements there are 2^n subsets. The doubling also explains why no duplicates appear: every subset created in a pass contains the element just processed, so it cannot match any subset from an earlier pass.
Algorithm
- Initialize the result with the empty subset: [[]].
- For each number in the input array:
- Look at every subset currently in the result.
- Create a new subset by appending the current number to each existing subset.
- 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 copies a growing collection of subsets at every step. The backtracking approach builds one subset incrementally and copies it only when recording a result, which keeps the working memory down to a single subset.
Approach 2: Backtracking
Intuition
Backtracking builds one subset incrementally and records it at every step. The recursion iterates through the remaining elements starting from a given index. At each call it picks the next element to add, recurses, then removes that element to restore the previous state before trying the next one.
The start index is what prevents duplicates. Each call only considers elements at index >= start, so an element is never chosen before an element that already precedes it in the current subset. Every subset is therefore built in increasing index order, and there is exactly one such ordering per subset.
Recording a result at every call, rather than only at a base case, is what distinguishes subsets from combinations or permutations. Every partial selection is itself a valid subset, from the empty set up to the full array, so each recursive call adds one subset to the result.
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:
- Add nums[i] to the current subset.
- Recurse with start index = i + 1.
- Remove nums[i] from the current subset (backtrack).
- The recursion terminates when the start index reaches the array length, since the loop then makes no iterations.
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.
The iterative and backtracking approaches share the same time complexity. A third approach uses bit manipulation, mapping each subset to a binary number and removing recursion entirely.
Approach 3: Bit Manipulation
Intuition
For an array of n elements, there are 2^n subsets and also 2^n binary numbers from 0 to 2^n - 1. Each n-bit number encodes one subset: if bit j is 1, element j is included; if bit j is 0, element j is excluded. Since distinct numbers have distinct bit patterns, this mapping is one-to-one, so iterating over all 2^n numbers produces all 2^n subsets with no duplicates.
We generate every subset by iterating from 0 to 2^n - 1 and, for each number, reading which bits are set to decide which elements belong. This needs no recursion and no backtracking, only 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:
- Create a new subset.
- For each bit position j from 0 to n - 1: if bit j of mask is set, add nums[j] to the subset.
- 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.