Generate All Subsets — Problem Statement & Solution Guide
Problem Description
You are given an array of integers nums. Your task is to produce every possible subset (also known as a power set) that can be formed from the elements of nums. A subset may contain any number of elements from zero up to the full length of the array, and each element can appear at most once in a subset. The output should be a list of subsets; the order of the subsets and the order of elements within each subset are not important. Each subset must be represented as an array of integers, and the collection of subsets must be represented as an array of these arrays.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Generate All Subsets"
WHY DOES IT MATTER?
Generating subsets is a canonical example of the combinatorial explosion pattern, teaching candidates how to handle problems where the output size itself is exponential. Mastery of this pattern signals the ability to design algorithms that respect output-sensitive complexity and avoid unnecessary overhead.
OPTIMIZATION CHALLENGE
The key insight is to treat subset construction as a binary decision tree, allowing either a recursive backtrack or an iterative bit‑mask loop that directly maps each integer to a subset, thereby eliminating redundant scans and achieving O(2^n) time, which is optimal given the output size.
REAL-WORLD CONNECTION
In feature flag management for large SaaS platforms, each flag can be on or off, creating a power set of possible configurations. Engineers often need to test or rollout a subset of these configurations, mirroring the subset generation process.
During an interview, write the backtracking skeleton first (choose/skip) and then fill in the base case; if you get stuck, switch to the bit‑mask loop—its one‑liner body often reveals bugs faster.
COMPLEXITY AT A GLANCE
O(2^n * n)O(2^n * n) (output) + O(n) (recursion stack or current subset)Core Theory — Why This Approach?
The power set of a set with n elements contains 2^n subsets because each element has two independent choices: either it is included or it is excluded. A naive enumeration that tries to generate subsets by repeatedly scanning the array for combinations quickly becomes infeasible as n grows, since the total number of subsets grows exponentially and any algorithm that does more than O(2^n) work per subset will time out. The optimal paradigm leverages binary representation or backtracking to systematically explore the inclusion‑exclusion decision tree, ensuring that each subset is built in O(1) amortized time relative to the output size. By treating each recursive level as a binary decision, we can either add the current element to the working subset or skip it, then recurse on the remainder, which yields a clean O(2^n) time algorithm that matches the lower bound dictated by the output size. This approach also naturally supports iterative bit‑masking, where the i‑th bit of a number from 0 to 2^n‑1 indicates whether the corresponding element is present, allowing a compact loop without recursion.
Interview Questions on This Problem
Q1How would you generate all subsets of an array that may contain duplicate elements while ensuring each subset is unique?
Sort the array first, then use backtracking with a conditional skip: when encountering a duplicate element, only include it in a new subset if the previous identical element was included in the current recursion path. This prevents generating identical subsets caused by duplicate values.
Q2Explain the relationship between the number of subsets and the binary representation of integers from 0 to 2^n‑1.
Each integer in that range can be expressed with n bits; the j‑th bit indicates whether the j‑th element of the input array is present in the subset. Iterating over all integers thus enumerates every possible inclusion‑exclusion combination, guaranteeing all 2^n subsets.
Q3In a distributed system, how could you parallelize the generation of subsets for a very large n, and what challenges arise?
Partition the range of bit masks among workers (e.g., each worker handles a contiguous block of integers). The main challenges are load balancing (since the work per mask is uniform, simple range partition works) and aggregating results without overwhelming network bandwidth; using streaming or map‑reduce style collection mitigates this.
Examples
Input
[1,2]
Output
[[],[1],[2],[1,2]]
Explanation: The array has two elements. The subsets are: 1. The empty subset: [] 2. Subset containing only the first element: [1] 3. Subset containing only the second element: [2] 4. Subset containing both elements: [1, 2] All four combinations are listed.
Input
[3]
Output
[[],[3]]
Explanation: With a single element, there are only two subsets: 1. The empty subset: [] 2. The subset containing the element: [3]
Input
[1,2,3]
Output
[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
Explanation: For three elements, the power set contains 2^3 = 8 subsets. They are enumerated as: - [] - [1] - [2] - [3] - [1, 2] - [1, 3] - [2, 3] - [1, 2, 3] Each subset is formed by choosing a unique combination of the three numbers.
Constraints
- 1 <= nums.length <= 20
- -10^9 <= nums[i] <= 10^9
- All elements in nums are distinct
- The total number of subsets must fit within the available memory
- The algorithm should run in O(2^n) time, where n is nums.length
Optimal Approach & Strategy
Use either recursive backtracking (choose/skip) or an iterative bit‑mask loop where each integer's binary representation dictates element inclusion, achieving O(2^n) time with minimal extra work.
Brute Force Approach
Generate every possible combination by repeatedly scanning the array and building subsets using nested loops or repeated concatenation, leading to exponential time with additional overhead for each subset.
Verified Code Solutions
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function(nums) {
const result = [];
const current = [];
const backtrack = (start) => {
result.push([...current]);
for (let i = start; i < nums.length; i++) {
current.push(nums[i]);
backtrack(i + 1);
current.pop();
}
};
backtrack(0);
return result;
};class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
vector<int> current;
function<void(int)> backtrack = [&](int start) {
result.push_back(current);
for (int i = start; i < nums.size(); ++i) {
current.push_back(nums[i]);
backtrack(i + 1);
current.pop_back();
}
};
backtrack(0);
return result;
}
};class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> current = new ArrayList<>();
backtrack(nums, 0, current, result);
return result;
}
private void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
result.add(new ArrayList<>(current));
for (int i = start; i < nums.length; i++) {
current.add(nums[i]);
backtrack(nums, i + 1, current, result);
current.remove(current.size() - 1);
}
}
}class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
current = []
def backtrack(start):
result.append(current[:])
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1)
current.pop()
backtrack(0)
return result/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function(nums) {
const result = [];
const current = [];
const backtrack = (start) => {
result.push([...current]);
for (let i = start; i < nums.length; i++) {
current.push(nums[i]);
backtrack(i + 1);
current.pop();
}
};
backtrack(0);
return result;
};Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.