AlgoViz
HomeBit Manipulation

Power Set Bit Manipulation

Medium

Each number 0..2^n-1 is a subset

Problem

Generate all subsets of a set using bitmasks: each number 0..2^n-1 encodes which elements are chosen.

In simple words

For each element, decide keep-or-skip — every combination of those choices is a subset.

The idea

Treat the bits of a counter as include/exclude flags: bit i set means element i is in the subset. Counting from 0 to 2^n - 1 therefore enumerates every subset exactly once, with no recursion at all.

The trick

  • Include element i when `(mask >> i) & 1`.
  • 2^n masks, each read in O(n) — O(2^n · n) overall.
  • Only practical up to n around 20.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
3
0
1
2

Step 1 of 2. Here's the example — [1,2,3] Values: 1, 2, 3.

1/2
Optimal
timeO(n*2^n)spaceO(n)
1for mask in 0..(1<<n)-1:2  subset=[]3  for i in 0..n-1: if mask & (1<<i): subset.push(nums[i])4  output subset

Input

array
[1, 2, 3]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 2, 3]
Output:
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Explanation:
All 2^3 = 8 subsets.

Example 2

Input:
nums = [1, 2]
Output:
[[], [1], [2], [1, 2]]
Explanation:
4 subsets including the empty set.

Example 3

Input:
nums = [0]
Output:
[[], [0]]
Explanation:
Just {} and {0}.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.