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.

Practice

1. What does the term powerset mean in the context of sets?

easy

A. All possible subsets of a given set, including empty and full set

B. Only the subsets with exactly half the elements of the set

C. The set of elements that are not in the original set

D. The set containing only the largest element of the original set

Solution

1. Step 1: Understand the definition of powerset

   The powerset of a set is the collection of all subsets, including the empty set and the set itself.

2. Step 2: Compare options with definition

   All possible subsets of a given set, including empty and full set correctly describes all subsets, while others describe partial or unrelated sets.

3. Final Answer:

   All possible subsets of a given set, including empty and full set -> Option A

4. Quick Check:

   powerset = all subsets [OK]

Hint: Remember powerset means every subset possible [OK]

Common Mistakes:

• Thinking powerset excludes empty set
• Confusing powerset with complement set
• Assuming powerset only has subsets of certain size

2. Which of the following TypeScript function signatures correctly represents a function that generates all subsets of an array of numbers?

easy

A. function generateSubsets(nums: number[][]): number[]

B. function generateSubsets(nums: number): number[]

C. function generateSubsets(nums: string[]): string

D. function generateSubsets(nums: number[]): number[][]

Solution

1. Step 1: Analyze the input and output types

   The input is an array of numbers, so nums: number[] is correct. The output is all subsets, so an array of arrays of numbers number[][] is expected.

2. Step 2: Match options with correct types

   function generateSubsets(nums: number[]): number[][] matches input and output types correctly. Others have mismatched types or wrong return types.

3. Final Answer:

   function generateSubsets(nums: number[]): number[][] -> Option D

4. Quick Check:

   Input array, output array of arrays [OK]

Hint: Input array, output array of arrays for subsets [OK]

Common Mistakes:

• Returning a flat array instead of array of arrays
• Using wrong input type like number instead of number[]
• Returning a string instead of array

3. What is the output of the following TypeScript code?

function subsets(nums: number[]): number[][] {
  const result: number[][] = [[]];
  for (const num of nums) {
    const newSubsets = result.map(subset => [...subset, num]);
    result.push(...newSubsets);
  }
  return result;
}

console.log(subsets([1, 2]));

medium

A. [[], [1], [2], [1, 2]]

B. [[1], [2], [1, 2]]

C. [[], [1, 2]]

D. [[], [1], [2]]

Solution

1. Step 1: Trace the initial state and loop

   Start with result = [[]]. For num=1, newSubsets = [[1]], result becomes [[], [1]]. For num=2, newSubsets = [[2], [1, 2]], result becomes [[], [1], [2], [1, 2]].

2. Step 2: Confirm final output

   The function returns all subsets: empty, single elements, and full set.

3. Final Answer:

   [[], [1], [2], [1, 2]] -> Option A

4. Quick Check:

   All subsets of [1,2] listed [OK]

Hint: Each loop doubles subsets by adding current number [OK]

Common Mistakes:

• Forgetting to include empty subset
• Not spreading new subsets correctly
• Returning partial subsets only

4. Identify the error in this TypeScript code that tries to generate all subsets:

function getSubsets(nums: number[]): number[][] {
  let result: number[][] = [];
  for (const num of nums) {
    const newSubsets = result.map(subset => [...subset, num]);
    result = [...result, ...newSubsets];
  }
  return result;
}

console.log(getSubsets([1, 2]));

medium

A. The spread operator is missing in the return statement

B. The map function is used incorrectly

C. The initial result should contain the empty subset [[]]

D. The function should return a flat array, not array of arrays

Solution

1. Step 1: Check initial value of result

   The code starts with result = [], missing the empty subset []. This causes no subsets to be generated.

2. Step 2: Understand impact on loop

   Since result is empty initially, result.map returns empty array each time, so no subsets are added.

3. Final Answer:

   The initial result should contain the empty subset [[]] -> Option C

4. Quick Check:

   Start with [[]] to build subsets [OK]

Hint: Always start subsets with empty set [[]] [OK]

Common Mistakes:

• Starting with empty array instead of array with empty subset
• Misusing map without initial subsets
• Expecting output without base case

5. Given an array nums = [1, 2, 2], which of the following outputs correctly represents all unique subsets (powerset without duplicates) generated by a function that handles duplicates?

hard

A. [[], [1], [2], [2, 2]]

B. [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]]

C. [[], [1], [2], [1, 2], [1, 2, 2]]

D. [[], [1], [2], [1, 2], [2, 2], [1, 2, 2], [2, 1]]

Solution

1. Step 1: Understand duplicates in input

   The input has duplicate '2's. The powerset must include subsets with one or two '2's but no repeated subsets.

2. Step 2: List all unique subsets

   Subsets are: empty [], single elements [1], [2], pairs [1,2], [2,2], and triple [1,2,2]. [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]] lists all correctly without duplicates.

3. Final Answer:

   [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]] -> Option B

4. Quick Check:

   Include duplicates subsets once [OK]

Hint: Handle duplicates by sorting and skipping repeats [OK]

Common Mistakes:

• Including duplicate subsets multiple times
• Missing subsets with two duplicates
• Adding permutations like [2,1] as separate subset