Log inSign up
mediumLeetCodeNot Started

Power Set

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

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.

An array of n elements has exactly 2^n subsets.

Example 1 · Example 1: Three Elements:

Input: nums = [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Explanation: 23 = 8 subsets total.

Example 2 · Example 2: Single Element:

Input: nums = [0]
Output: [[], [0]]
Explanation: 21 = 2 subsets total.

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All the numbers of nums are unique.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Map combinatorial subsets directly to binary integer representations.
  • Extract constituent elements using bitmask tests: (mask >> j) & 1.
  • Compare recursive backtracking vs iterative bit manipulation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Generate all possible combinations or subsets.
  • n is small (typically n <= 16).
  • Binary decision tree (pick or don't pick each element).

Algorithmic Decision Tree:

  • Loop mask from 0 to (1 << n) - 1.
  • For bit j from 0 to n - 1: if mask has bit j set, include nums[j].

Connected Patterns:

Subsets XOR SumCombinationsPermutations

1. Cascading Iteration

Intuition

Initialize result = [[]]. For each element num in nums, take every existing subset currently in result, create a copy with num appended, and add the new subset back into result.

When to apply: When building subsets intuitively without bit logic or recursion.

Algorithm

  1. Step 1: Initialize result = [[]].
  2. Step 2: For each num in nums:
  3. Step 3: For each subset in current result: copy subset, append num, push to result.
  4. Step 4: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6vector<vector<int>> subsetsCascading(vector<int>& nums) {
7 vector<vector<int>> res = {{}};
8 for (int num : nums) {
9 int n = res.size();
10 for (int i = 0; i < n; ++i) {
11 vector<int> sub = res[i];
12 sub.push_back(num);
13 res.push_back(sub);
14 }
15 }
16 return res;
17}
18
19int main() {
20 vector<int> nums = {1, 2};
21 auto res = subsetsCascading(nums);
22 cout << "Cascading size: " << res.size() << endl; // 4
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(n * 2^n)
  • Space complexity: O(1) auxiliary space

2. Backtracking (DFS)

Intuition

Maintain a current path array. At each index idx, either skip nums[idx] and recurse, or include nums[idx] and recurse. When idx == n, push the current subset to result.

When to apply: Standard template when subset filtering constraints are involved.

Algorithm

  1. Step 1: Define helper(idx, currentSubset).
  2. Step 2: If idx == n, push currentSubset to result, return.
  3. Step 3: Branch 1: include nums[idx], helper(idx + 1).
  4. Step 4: Branch 2: exclude nums[idx], helper(idx + 1).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6void dfs(int idx, vector<int>& nums, vector<int>& curr, vector<vector<int>>& res) {
7 if (idx == (int)nums.size()) {
8 res.push_back(curr);
9 return;
10 }
11 // Exclude
12 dfs(idx + 1, nums, curr, res);
13 // Include
14 curr.push_back(nums[idx]);
15 dfs(idx + 1, nums, curr, res);
16 curr.pop_back();
17}
18
19vector<vector<int>> subsetsDFS(vector<int>& nums) {
20 vector<vector<int>> res;
21 vector<int> curr;
22 dfs(0, nums, curr, res);
23 return res;
24}
25
26int main() {
27 vector<int> nums = {1, 2};
28 auto res = subsetsDFS(nums);
29 cout << "DFS size: " << res.size() << endl; // 4
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(n * 2^n)
  • Space complexity: O(n) recursion call stack

3. Bitmasking (Iterative Bit Representation)

Intuition

Iterate mask from 0 to (1 << n) - 1. For each mask, create an empty list. Check each bit index j from 0 to n - 1: if (mask & (1 << j)) != 0, append nums[j] to the current list. Push the constructed subset to result.

When to apply: Optimal canonical solution for power set generation.

Algorithm

  1. Step 1: totalSubsets = 1 << n.
  2. Step 2: Loop mask from 0 to totalSubsets - 1.
  3. Step 3: sub = [].
  4. Step 4: Loop j from 0 to n - 1: if (mask & (1 << j)) != 0, sub.push(nums[j]).
  5. Step 5: res.push(sub).
  6. Step 6: Return res.

Bitmask Subset Generation Trace: nums = [1, 2]

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Mask 0 (binary 00): bit 0 is 0, bit 1 is 0
Visual state
Values and pointers at this exact step
pointers
S
[]
0
↑ 00
Check / comparison
mask = 00_2
Decision / next transition
Add [] to power set.
Why this step matters

Mask 0 (binary 00): bit 0 is 0, bit 1 is 0. Subset = [].

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 vector<vector<int>> subsets(vector<int>& nums) {
9 int n = nums.size();
10 int totalSubsets = 1 << n;
11 vector<vector<int>> res;
12 res.reserve(totalSubsets);
13
14 for (int mask = 0; mask < totalSubsets; ++mask) {
15 vector<int> sub;
16 for (int j = 0; j < n; ++j) {
17 if ((mask >> j) & 1) {
18 sub.push_back(nums[j]);
19 }
20 }
21 res.push_back(sub);
22 }
23 return res;
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<int> nums = {1, 2, 3};
30 auto res = sol.subsets(nums);
31 cout << "Optimal Bitmask size: " << res.size() << endl; // 8
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(n * 2^n)
  • Space complexity: O(1) auxiliary space (excluding result)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Cascading IterationO(n * 2^n)O(1) auxiliaryStart with [[]]. For each element num, duplicate all existing subsets and append num.Array cloning.
2.Better — Backtracking (DFS)O(n * 2^n)O(n) recursion stackRecursive pick / don't pick tree branching at each index from 0 to n - 1.Recursion depth.
3.Optimal — Binary BitmaskingOptimalO(n * 2^n)O(1) auxiliaryIterate mask from 0 to (1 << n) - 1. Construct each subset by testing bit j.Output construction.

Common Pitfalls & Crucial Edge Cases

Shift overflow for n >= 31

In C++/Java, 1 << n on standard signed 32-bit int invokes undefined behavior or wraps negative when n = 31. Use 1ULL << n or 1L << n.

Forgetting the empty subset

The empty subset corresponds to mask = 0 and must be included.

Modifying subset arrays after pushing

In JavaScript, ensure you push a new array instance rather than reusing a mutable buffer.

Crucial Edge Cases to Validate:

  • Empty array `nums = []` — Returns [[]] (one empty subset).
  • Single element `nums = [1]` — Returns [[], [1]].
  • Large n (n > 30) — 1 << n overflows 32-bit integers; bitmasking is limited to n <= 30 (for 64-bit masks, n <= 60).
  • Array with duplicate values — If unique subsets are requested, bitmasking requires sorting and deduplication.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain why bitmasking is iterative, avoiding recursive call stack overhead.
  2. Discuss the constraint boundary: bitmasking is ideal when n <= 20, as 220 is approximately 106 operations.
  3. Compare bit manipulation with backtracking/recursion and discuss memory locality.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How many total subsets exist for a set of n elements?

2.How does bitmasking generate every subset from an integer mask in [0, 2n - 1]?

3.What is the total time complexity to generate all subsets using bit manipulation?

Back to DSA Sheet