Generate All Subsets Powerset in DSA Typescript - Build from Scratch

Generate All Subsets (Powerset)

📖 Scenario: Imagine you have a small collection of unique items, like three different colored marbles. You want to find all the possible groups you can make from these marbles, including the empty group and the group with all marbles.

🎯 Goal: Build a TypeScript program that takes a list of unique numbers and generates all possible subsets (the powerset) of that list.

📋 What You'll Learn

Create an array called nums with the exact values [1, 2, 3].

Create a variable called result to hold all subsets, starting with an empty subset.

Use a for loop to go through each number in nums.

Inside the loop, use another for loop to add the current number to existing subsets and add these new subsets to result.

Print the final result array showing all subsets.

💡 Why This Matters

🌍 Real World

Generating all subsets is useful in situations like choosing combinations of items, testing all possible feature sets in software, or exploring different groupings in data analysis.

💼 Career

Understanding how to generate powersets helps in problem solving, algorithm design, and is often asked in coding interviews for software engineering roles.

1

Create the initial array

Create an array called nums with the exact values [1, 2, 3].

DSA Typescript

# Create the array nums with values [1, 2, 3]
// Your code here

Hint

Use const nums = [1, 2, 3]; to create the array.

2

Create the result array with an empty subset

Create a variable called result and set it to an array containing an empty array [[]] to start with the empty subset.

DSA Typescript

const nums = [1, 2, 3];
// Create result array with an empty subset
// Your code here

Hint

Use const result: number[][] = [[]]; to start with an empty subset.

3

Generate all subsets using loops

Use a for loop with variable num to go through nums. Inside it, use another for loop with variable i to go through result. For each subset at index i, create a new subset by adding num to it and add this new subset to result.

DSA Typescript

const nums = [1, 2, 3];
const result: number[][] = [[]];
// Use nested loops to generate all subsets
// Your code here

Hint

Use for (const num of nums) and inside it for (let i = 0; i < length; i++). Add new subsets with result.push([...curr, num]).

4

Print the final result

Print the result array to show all subsets.

DSA Typescript

const nums = [1, 2, 3];
const result: number[][] = [[]];
for (const num of nums) {
    const length = result.length;
    for (let i = 0; i < length; i++) {
        const curr = result[i];
        result.push([...curr, num]);
    }
}
// Print the result array
// Your code here

Hint

Use console.log(result); to print all subsets.

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