What is the time complexity of generating all subsets of an array of size n using bitmask enumeration, and why?

medium🪤 Complexity Trap Q5 of Q15

Subsets & Combinations - Subsets Using Bitmask

AO(n^2) because each subset requires scanning all elements

BO(2^n) because subsets are generated directly without scanning elements

CO(n * 2^n) because there are 2^n subsets and each subset takes O(n) to build

DO(n) because bitmasking is constant time per subset

Step-by-Step Solution

Solution:

Step 1: Count subsets
There are 2^n subsets for n elements.
Step 2: Time per subset
Each subset requires checking up to n bits to build the subset list.
Final Answer:
Option C -> Option C
Quick Check:
Time = O(n * 2^n) due to subset count and element checks [OK]

Quick Trick: 2^n subsets x n elements each [OK]

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

Candidates often forget that building each subset requires scanning elements, leading to underestimating complexity.

Interviewer Note:

CONTEXT

Master "Subsets Using Bitmask" in Subsets & Combinations

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

More Subsets & Combinations Quizzes