What is the time and space complexity of Subsets?

Time complexity: O(n * 2^n). Space complexity: O(n * 2^n).

Subsets

Med

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Subsets

Approach

Enumerate all 2^n bitmasks from 0 to 2^n - 1. For each mask, include element i in the subset whenever bit i is set (mask & (1 << i)). Each mask uniquely represents one subset of the input array.

Complexity Analysis

Time: O(n * 2^n)
Space: O(n * 2^n)

Pattern

Bitmask Enumeration

Why It Works

There is a one-to-one correspondence between n-bit binary numbers and subsets of an n-element set, so iterating all masks generates every possible subset exactly once.

Updated Mar 2026