Generate All Subsets Powerset in DSA Javascript - Build from Scratch

Generate All Subsets Powerset

📖 Scenario: Imagine you have a small collection of unique fruits and you want to find all possible combinations of these fruits. This is useful when you want to explore every possible selection you can make from your collection.

🎯 Goal: You will build a program that generates all subsets (the powerset) of a given list of fruits. Each subset represents a possible combination of fruits you can pick.

📋 What You'll Learn

Create an array called fruits with the exact values 'apple', 'banana', and 'cherry'.

Create an empty array called result to store all subsets.

Write a function called generateSubsets that takes two parameters: index and currentSubset.

Use recursion inside generateSubsets to explore all subsets by either including or excluding the current fruit.

Call generateSubsets starting with index 0 and an empty array for currentSubset.

Print the result array after generating all subsets.

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding how to generate powersets is important for software engineers working on algorithms, combinatorics problems, and optimization tasks.

1

Create the initial array of fruits

Create an array called fruits with these exact values: 'apple', 'banana', and 'cherry'.

DSA Javascript

# Your code here

Hint

Use square brackets [] to create an array and separate the fruit names with commas.

2

Create an empty array to store subsets

Create an empty array called result to store all subsets.

DSA Javascript

const fruits = ['apple', 'banana', 'cherry'];
# Your code here

Hint

Use [] to create an empty array and assign it to result.

3

Write the recursive function to generate subsets

Write a function called generateSubsets that takes two parameters: index and currentSubset. Use recursion to explore all subsets by either including or excluding the current fruit. Inside the function, if index equals the length of fruits, push a copy of currentSubset to result and return. Otherwise, call generateSubsets twice: once including fruits[index] in currentSubset, and once excluding it.

DSA Javascript

const fruits = ['apple', 'banana', 'cherry'];
const result = [];

# Your code here

Hint

Use if to check if index reached the end. Use push and pop to add and remove fruits from currentSubset. Call the function recursively twice to include and exclude the current fruit.

4

Call the function and print all subsets

Call generateSubsets starting with index 0 and an empty array for currentSubset. Then print the result array.

DSA Javascript

const fruits = ['apple', 'banana', 'cherry'];
const result = [];

function generateSubsets(index, currentSubset) {
    if (index === fruits.length) {
        result.push([...currentSubset]);
        return;
    }
    // Exclude the current fruit
    generateSubsets(index + 1, currentSubset);
    // Include the current fruit
    currentSubset.push(fruits[index]);
    generateSubsets(index + 1, currentSubset);
    currentSubset.pop();
}

# Your code here

Hint

Call generateSubsets(0, []) to start. Use console.log(result) to print all subsets.

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