Overview
Subset generation lists every possible selection of elements, including the empty set. An array of n elements has 2^n subsets, because each element is either included or excluded. This take / not-take choice is the most fundamental recursion pattern and appears throughout DP and backtracking.
There are three standard ways to generate subsets: recursive take / skip, iterative expansion (start with [[]] and append each element to every existing subset), and bitmasks (each integer from 0 to 2^n - 1 encodes one subset). Handling duplicates correctly (Subsets II) is the common follow-up.
For each item on your list, you decide: pack it or leave it. With 3 items there are 2 x 2 x 2 = 8 possible bags, from the empty bag to the bag with everything.
When to use it
- All subsets or all subsequences are required.
- n is small (up to about 20), so 2^n is feasible.
- The answer is some aggregate over all subsets (XOR totals, sums).
- As a building block for meet-in-the-middle and bitmask DP.
Problem patterns it solves
Recognize it when: enumerate every selection of elements.
- 78. Subsets
- 1863. Sum of All Subset XOR Totals
- 2044. Count Number of Maximum Bitwise-OR Subsets
Recognize it when: input has repeated values; output must be unique.
- 90. Subsets II
- 491. Non-decreasing Subsequences
Recognize it when: n <= 20 and subsets map naturally to bits.
- 78. Subsets (bitmask)
- 1239. Maximum Length of a Concatenated String with Unique Characters
- 2397. Maximum Rows Covered by Columns
Recognize it when: can a subset reach a target; count subsets with a sum.
- 416. Partition Equal Subset Sum
- 494. Target Sum
- 698. Partition to K Equal Sum Subsets
Where it is used in real software
Testing every combination of enabled features, or pairwise subsets of them, in combinatorial test suites.
The Apriori algorithm enumerates item subsets to find products frequently bought together.
Role and permission sets are subsets of all capabilities, often stored as bitmasks.
Key terms
- Power set
- The set of all subsets; size 2^n.
- Subsequence
- Elements in original order, not necessarily contiguous; one per subset.
- Bitmask
- Integer whose bit i says whether element i is included.
- Take / skip
- The binary choice made for each element.
How it works, step by step
- 1Recursive: index and path
At index i, first record or recurse skipping nums[i], then include nums[i] and recurse.
- 2Base case
When i === n, the path is one complete subset.
- 3Iterative expansion
Start with [[]]. For each number, copy every existing subset and append the number.
- 4Bitmask
For mask from 0 to 2^n - 1, include nums[i] when (mask >> i) & 1.
- 5Duplicates
Sort; when skipping a value, skip all its copies so identical subsets are not produced twice.
STEP 1Start with the empty subset.
Bitmask mapping for [a, b, c]
bit 0 = a, bit 1 = b, bit 2 = c
| mask | binary | subset |
|---|---|---|
| 0 | 000 | [] |
| 1 | 001 | [a] |
| 2 | 010 | [b] |
| 3 | 011 | [a, b] |
| 4 | 100 | [c] |
| 5 | 101 | [a, c] |
| 6 | 110 | [b, c] |
| 7 | 111 | [a, b, c] |
NOWmask: 0 | binary: 000 | subset: []
Every integer from 0 to 2^n - 1 is a different subset, so a single loop enumerates all of them without recursion.
Implementation
// Take / skip recursionfunction subsets(nums) { const result = [], path = []; function dfs(i) { if (i === nums.length) { result.push([...path]); return; } dfs(i + 1); // skip nums[i] path.push(nums[i]); // take nums[i] dfs(i + 1); path.pop(); } dfs(0); return result;} // Bitmaskfunction subsetsBitmask(nums) { const result = []; for (let mask = 0; mask < 1 << nums.length; mask++) { const subset = []; for (let i = 0; i < nums.length; i++) if ((mask >> i) & 1) subset.push(nums[i]); result.push(subset); } return result;} // 90. Subsets II: loop-based backtracking, skip duplicates at the same depthfunction subsetsWithDup(nums) { nums.sort((a, b) => a - b); const result = [], path = []; function backtrack(start) { result.push([...path]); // every node in the tree is a subset for (let i = start; i < nums.length; i++) { if (i > start && nums[i] === nums[i - 1]) continue; path.push(nums[i]); backtrack(i + 1); path.pop(); } } backtrack(0); return result;}Complexity and performance
2^n subsets, each copied in O(n).
Recursion depth and path.
Total elements across subsets.
Trade-offs
Bitmasks are compact and iterative but limited to about 30 elements per integer. Recursion handles pruning and duplicates more naturally.
If the question only asks whether a subset with sum k exists, DP over sums is polynomial in n x k, far faster than 2^n enumeration.
Variants and related techniques
That is combinations; stop when the path length reaches k.
Enumerate subsets so consecutive ones differ by one element.
for (sub = mask; sub; sub = (sub - 1) & mask) visits all submasks of mask.
Common mistakes
- 1 << n overflow in Java for n >= 31.
Fix: Subset enumeration is infeasible there anyway; use long or recursion for n up to about 25.
- Duplicates in Subsets II.
Fix: Sort first and skip equal values at the same recursion level.
- Iterative expansion reading a growing list.
Fix: Capture the size before the inner loop.
Interview questions
Why are there 2^n subsets?
Each of the n elements independently has two choices, in or out, so the total number of combinations is 2 x 2 x ... x 2 = 2^n.
How do you handle duplicates in the input?
Sort the array, then in the loop-based backtracking skip nums[i] when it equals nums[i - 1] and i > start, so the same value is not chosen twice at the same position.
Practice problems
| Problem | Difficulty | What it trains |
|---|---|---|
| 78. Subsets | Medium | All three methods. |
| 90. Subsets II | Medium | Duplicate skipping. |
| 1863. Sum of All Subset XOR Totals | Easy | Take / skip values. |
| 491. Non-decreasing Subsequences | Medium | Per-level set for duplicates. |
| 698. Partition to K Equal Sum Subsets | Medium | Subset search with pruning. |