Bird
Raised Fist0

What is the time complexity of generating all subsets of an array of size n using the bit manipulation approach shown below?

medium🪤 Complexity Trap Q13 of Q15
Subsets & Combinations - Subsets
What is the time complexity of generating all subsets of an array of size n using the bit manipulation approach shown below?
AO(2^n * n) because for each of the 2^n masks, we check n bits to build the subset
BO(2^n) because there are 2^n subsets and each subset is generated in constant time
CO(n^2) because of nested loops over n elements
DO(n * 2^n) because each of the 2^n subsets requires iterating over n elements
Step-by-Step Solution

  1. Step 1: Identify outer loop complexity

    The outer loop runs 2^n times, once per subset mask.

  2. Step 2: Identify inner loop complexity

    For each mask, the inner loop iterates n times to check each bit.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Total time is 2^n * n due to mask and bit checks [OK]
Quick Trick: Each subset requires checking n bits -> O(n*2^n) [OK]
Common Mistakes:
MISTAKES
  • Assuming subset generation is O(2^n) ignoring bit checks
  • Confusing n^2 with 2^n * n
Trap Explanation:
PITFALL
  • Option B looks plausible but ignores the cost of iterating over bits per subset.
Interviewer Note:
CONTEXT
  • Checks if candidate understands bitmask iteration cost, not just subset count.
Master "Subsets" in Subsets & Combinations

3 interactive learning modes - each teaches the same concept differently

Try ItSolutionTrace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Subsets & Combinations Quizzes
Combination Sum II (No Reuse, Duplicates) - Combination Sum II (No Reuse, Duplicates) - Quiz 2easy Combination Sum III (K Numbers to N) - Combination Sum III (K Numbers to N) - Quiz 6medium Count Number of Max Bitwise-OR Subsets - Count Number of Max Bitwise-OR Subsets - Quiz 3easy Count Number of Max Bitwise-OR Subsets - Count Number of Max Bitwise-OR Subsets - Quiz 4medium Count of Subsets With Sum K - Count of Subsets With Sum K - Quiz 4medium Letter Case Permutation - Letter Case Permutation - Quiz 6medium Matchsticks to Square - Matchsticks to Square - Quiz 8hard Matchsticks to Square - Matchsticks to Square - Quiz 10hard Partition to K Equal Sum Subsets - Partition to K Equal Sum Subsets - Quiz 2easy Subsets II (With Duplicates) - Subsets II (With Duplicates) - Quiz 15hard