Generate All Subsets Powerset in DSA Typescript

Mental Model

We want to find every possible group of items you can make from a list, including the empty group and the full list.

Analogy: Imagine you have a box of colored beads. You want to see all the different ways you can pick beads, from none at all to all of them together.

Input array: [1, 2]
All subsets:
[]
[1]
[2]
[1, 2]

Dry Run Walkthrough

Input: list: [1, 2]

Goal: Find all subsets of the list [1, 2], including empty and full subsets.

Step 1: Start with an empty subset []

[]

Why: We always include the empty subset as a starting point.

Step 2: Add 1 to existing subsets to create new subsets

[] and [1]

Why: For each existing subset, add the new element to form new subsets.

Step 3: Add 2 to all existing subsets ([], [1]) to create new subsets

[], [1], [2], [1, 2]

Why: Repeat the process for the next element to get all combinations.

Result:

[]
[1]
[2]
[1, 2]

Annotated Code

DSA Typescript

class Powerset {
  static generateSubsets(nums: number[]): number[][] {
    const result: number[][] = [[]]; // start with empty subset
    for (const num of nums) {
      const newSubsets: number[][] = [];
      for (const subset of result) {
        newSubsets.push([...subset, num]); // add current num to each existing subset
      }
      result.push(...newSubsets); // add new subsets to result
    }
    return result;
  }
}

// Driver code
const input = [1, 2];
const subsets = Powerset.generateSubsets(input);
for (const subset of subsets) {
  console.log(subset);
}

const result: number[][] = [[]]; // start with empty subset

Initialize result with empty subset to build upon

for (const num of nums) {

Iterate over each number in input list

for (const subset of result) {

For each existing subset, create new subsets by adding current number

newSubsets.push([...subset, num]); // add current num to each existing subset

Create new subset by adding current number to existing subset

result.push(...newSubsets); // add new subsets to result

Add all new subsets to the result list

Output

[]

[1]

[2]

[1, 2]

Complexity Analysis

Time: O(n * 2^n) because for each of the n elements, we double the number of subsets by adding the element to all existing subsets.

Space: O(2^n) because the total number of subsets grows exponentially with the number of elements.

vs Alternative: This iterative approach is easier to understand and implement than recursive backtracking, but both have similar exponential time and space costs.

Edge Cases

empty input list []

Returns [[]], only the empty subset.

DSA Typescript

const result: number[][] = [[]]; // start with empty subset

single element list [5]

Returns [] and [5] as subsets.

DSA Typescript

for (const num of nums) {

When to Use This Pattern

When you need to find all possible combinations or groups from a list, especially including empty and full sets, use the powerset generation pattern because it systematically builds all subsets.

Common Mistakes

Mistake: Not starting with the empty subset, so missing subsets that don't include any elements.
Fix: Initialize the result with [[]] to include the empty subset from the start.

Mistake: Modifying the result list while iterating over it, causing infinite loops or missed subsets.
Fix: Create a separate list for new subsets and add them after the iteration finishes.

Summary

Generates all possible subsets (the powerset) of a given list.

Use when you want to explore every combination of elements from a set.

Start with the empty subset and add each element to existing subsets to build new ones.