Generate All Subsets Powerset in DSA Javascript

Mental Model

We want to find every possible group of items 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 ways you can pick some beads or none at all, like making every possible necklace combination.

Set: [1, 2]
Subsets:
[]
[1]
[2]
[1, 2]

Dry Run Walkthrough

Input: list: [1, 2]

Goal: Find all subsets of the list, including empty and full sets

Step 1: Start with an empty subset [[]]

[[]]

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

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

[[], [1]]

Why: We create new subsets by adding 1 to each existing subset

Step 3: Add element 2 to all existing subsets to create new subsets

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

Why: We add 2 to each existing subset to get all combinations including 2

Result:

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

Annotated Code

DSA Javascript

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

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

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

initialize result with empty subset

for (const num of nums) {

iterate over each number in input list

for (const subset of result) {

for each existing subset, create new subset with current number

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

extend subset by adding current number

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

add all new subsets to the result list

return result;

return all subsets generated

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 approach is efficient and clear compared to recursive backtracking which also has O(2^n) time but more complex call stack management

Edge Cases

empty list []

returns [[]] which is the powerset containing only the empty subset

DSA Javascript

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

list with one element [5]

returns [[], [5]] including empty and single element subsets

DSA Javascript

for (const num of nums) {

When to Use This Pattern

When you need to find all possible combinations or groups from a set, use the powerset generation pattern because it systematically builds every subset.

Common Mistakes

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

Mistake: Not including the empty subset at the start
Fix: Initialize result with [[]] to represent the empty subset

Summary

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

Use when you need every combination of elements from a set, including none or all.

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. The set itself without any subsets

B. All possible subsets of a set including the empty set

C. Only the subsets with exactly two elements

D. Subsets that contain only odd numbers

Solution

1. Step 1: Understand the definition of powerset

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

2. Step 2: Compare options with the definition

   All possible subsets of a set including the empty set correctly describes the powerset as all possible subsets including the empty set. Other options describe only parts or incorrect subsets.

3. Final Answer:

   All possible subsets of a set including the empty set -> Option B

4. Quick Check:

   powerset = all subsets [OK]

Hint: Powerset means every subset, even empty one [OK]

Common Mistakes:

• Thinking powerset excludes empty set
• Confusing powerset with subsets of fixed size
• Assuming powerset is just the original set

2. Which of the following JavaScript function signatures correctly represents a function to generate all subsets of an array arr?

easy

A. function generateSubsets(arr, subsets) { ... }

B. function generateSubsets(arr[]) { ... }

C. function generateSubsets() { ... }

D. function generateSubsets(arr) { ... }

Solution

1. Step 1: Check valid JavaScript function syntax

   function generateSubsets(arr) { ... } uses correct syntax with one parameter named arr. function generateSubsets(arr[]) { ... } uses invalid syntax with arr[]. function generateSubsets() { ... } has no parameters, which is incomplete for this task. function generateSubsets(arr, subsets) { ... } has two parameters which might be valid but is not the standard signature for generating subsets.

2. Step 2: Choose the most appropriate signature

   function generateSubsets(arr) { ... } is the standard and correct way to define a function that takes an array to generate subsets.

3. Final Answer:

   function generateSubsets(arr) { ... } -> Option D

4. Quick Check:

   Correct function syntax = function generateSubsets(arr) { ... } [OK]

Hint: Function parameters must be valid identifiers without brackets [OK]

Common Mistakes:

• Using array syntax in parameter list (arr[])
• Omitting required parameters
• Adding unnecessary parameters without explanation

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

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

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

medium

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

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

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

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

Solution

1. Step 1: Trace the initial result and loop

   Initially, 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 [[], [1], [2], [1, 2]] which matches [[], [1], [2], [1, 2]] exactly.

3. Final Answer:

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

4. Quick Check:

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

Hint: Each new number doubles subsets by adding to existing ones [OK]

Common Mistakes:

• Missing empty subset in output
• Not adding new subsets correctly
• Confusing order of subsets

4. Identify the error in this JavaScript code that tries to generate all subsets of nums:

function getSubsets(nums) {
  let result = [];
  for (let num of nums) {
    let newSubsets = [];
    for (let subset of result) {
      newSubsets.push(subset.concat(num));
    }
    result = result.concat(newSubsets);
  }
  return result;
}

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

medium

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

B. Using concat instead of push causes error

C. The inner loop should iterate over nums, not result

D. Missing return statement

Solution

1. Step 1: Check initial value of result

   The code initializes result as an empty array []. It should start with [[]] to include the empty subset, otherwise no subsets are generated.

2. Step 2: Understand impact of initial value

   Without the empty subset, the inner loop never runs on first iteration, so no subsets are created. Adding [[]] fixes this.

3. Final Answer:

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

4. Quick Check:

   Start with [[]] to generate subsets [OK]

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

Common Mistakes:

• Starting with empty array instead of [[]]
• Confusing concat and push usage
• Looping over wrong array

5. Given an array nums = [1, 2, 2], which code modification correctly generates all unique subsets (no duplicates) using the powerset approach?

hard

A. Remove duplicates from nums before generating subsets

B. Use a Set to store subsets as strings to avoid duplicates

C. Sort nums first, then skip adding duplicate subsets during generation

D. Generate all subsets normally without any change

Solution

1. Step 1: Understand the problem with duplicates

   Array [1, 2, 2] has duplicates. Generating subsets normally will create duplicate subsets like [2] twice.

2. Step 2: Apply sorting and skipping duplicates

   Sorting nums makes duplicates adjacent. During subset generation, skip adding subsets that duplicate previous ones to avoid duplicates in result.

3. Final Answer:

   Sort nums first, then skip adding duplicate subsets during generation -> Option C

4. Quick Check:

   Sort and skip duplicates to get unique subsets [OK]

Hint: Sort array and skip duplicates while generating subsets [OK]

Common Mistakes:

• Ignoring duplicates causing repeated subsets
• Removing duplicates from input changes problem
• Using Set of strings can be inefficient or incorrect