Generate All Subsets Powerset in DSA Typescript - Time & Space Complexity

Time Complexity: Generate All Subsets Powerset

O(n * 2^n)

Understanding Time Complexity

We want to understand how the time needed grows when we find all subsets of a set.

How does the work increase as the input set gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function generateSubsets(nums: number[]): number[][] {
  const result: number[][] = [];
  function backtrack(start: number, subset: number[]) {
    result.push([...subset]);
    for (let i = start; i < nums.length; i++) {
      subset.push(nums[i]);
      backtrack(i + 1, subset);
      subset.pop();
    }
  }
  backtrack(0, []);
  return result;
}
    

This code finds all subsets (the powerset) of the input array by exploring choices recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls that explore each subset possibility.
• How many times: Each element can be either included or excluded, so about 2ⁿ subsets are generated.

How Execution Grows With Input

As the input size grows, the number of subsets doubles for each new element.

Input Size (n)	Approx. Operations
10	About 1,024 subsets
20	About 1,048,576 subsets
30	About 1,073,741,824 subsets

Pattern observation: The work doubles with each added element, growing very fast.

Final Time Complexity

Time Complexity: O(n * 2n)

This means the time grows very fast because we must build all subsets, and each subset can take up to n steps to copy.

Common Mistake

[X] Wrong: "Generating all subsets is just O(n) because we just loop through the array once."

[OK] Correct: We actually explore every combination of elements, which grows exponentially, not linearly.

Interview Connect

Understanding this exponential growth helps you explain why some problems take longer and shows you can reason about complex recursive solutions.

Self-Check

"What if we only wanted subsets of a fixed size k? How would the time complexity change?"