What is the space complexity of the recursive backtracking approach to generate all subsets of an array of size n?

medium🪤 Complexity Trap Q6 of Q15

Subsets & Combinations - Subsets Using Bitmask

AO(2^n) only for storing results

BO(n) for recursion stack only

CO(n * 2^n) for storing all subsets plus O(n) recursion stack

DO(1) constant space since subsets are generated on the fly

Step-by-Step Solution

Solution:

Step 1: Storage for subsets
All subsets require O(n * 2^n) space to store in result.
Step 2: Recursion stack space
Recursion depth is O(n), so stack space is O(n).
Step 3: Total space complexity
Total space is dominated by storing subsets: O(n * 2^n). The recursion stack is additional O(n).
Final Answer:
Option C -> Option C
Quick Check:
Space = subsets storage + recursion stack [OK]

Quick Trick: Store all subsets plus recursion stack [OK]

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

Candidates often forget recursion stack space or underestimate total space needed.

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