Subsets Generation Using Bitmask in DSA Python - Time & Space Complexity

Time Complexity: Subsets Generation Using Bitmask

O(n * 2^n)

Understanding Time Complexity

We want to understand how the time needed to generate all subsets grows as the input size increases.

How does the number of operations change when we create subsets using bitmasks?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

nums = [1, 2, 3]
subsets = []
n = len(nums)
for mask in range(1 << n):
    subset = []
    for i in range(n):
        if mask & (1 << i):
            subset.append(nums[i])
    subsets.append(subset)
    

This code generates all subsets of the list nums using bitmasking.

Identify Repeating Operations

• Primary operation: The nested loops: outer loop runs over all bitmasks, inner loop checks each bit.
• How many times: Outer loop runs 2ⁿ times, inner loop runs n times for each outer iteration.

How Execution Grows With Input

As input size grows, the number of subsets doubles for each new element, and each subset requires checking all elements.

Input Size (n)	Approx. Operations
10	About 10 * 210 = 10,240
20	About 20 * 220 = 20,971,520
30	About 30 * 230 = 32,212,254,720

Pattern observation: The operations grow very fast, doubling with each added element and multiplying by n.

Final Time Complexity

Time Complexity: O(n * 2^n)

This means the time needed grows very quickly as input size increases, because we check every subset and every element.

Common Mistake

[X] Wrong: "Generating subsets is just O(2^n) because there are 2^n subsets."

[OK] Correct: We also spend time checking each element for every subset, so the inner loop adds a factor of n, making it O(n * 2^n).

Interview Connect

Understanding this complexity helps you explain why generating all subsets is expensive and shows your grasp of nested loops and exponential growth.

Self-Check

"What if we only generated subsets of a fixed size k instead of all sizes? How would the time complexity change?"