Generate All Subsets Powerset in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of powerset generation with duplicates

What is the output of the following JavaScript code that generates all subsets (powerset) of the array [1, 2, 2]?

DSA Javascript

function subsets(nums) {
  const result = [];
  nums.sort();
  function backtrack(start, path) {
    result.push([...path]);
    for (let i = start; i < nums.length; i++) {
      if (i > start && nums[i] === nums[i - 1]) continue;
      path.push(nums[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }
  backtrack(0, []);
  return result;
}
console.log(subsets([1, 2, 2]));

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

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

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

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

💡 Hint

Duplicates are skipped to avoid repeated subsets. The subsets are generated in sorted order.

The code sorts the input array and skips duplicates during recursion to avoid repeated subsets. The output is all unique subsets in sorted order.

❓ Predict Output

intermediate

Output of iterative powerset generation

What is the output of this iterative JavaScript code that generates all subsets of [1, 3]?

DSA Javascript

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

A [[],[1],[3],[1,3]]

B [[],[3],[1],[3,1]]

C [[],[1],[1,3],[3]]

D [[],[1],[3]]

💡 Hint

The code adds each number to all existing subsets to create new subsets.

The iterative method starts with an empty subset and adds each number to all existing subsets, doubling the count each time.

🧠 Conceptual

advanced

Number of subsets in powerset

Given an input array of length n, how many subsets does its powerset contain?

A 2^n

B n

C n^2

D n!

💡 Hint

Each element can either be included or excluded in a subset.

Each element has two choices: to be in or out of a subset. So total subsets = 2^n.

🔧 Debug

advanced

Identify the error in recursive powerset code

What error does this code produce when generating subsets of [1, 2]? function subsets(nums) { const result = []; function backtrack(start, path) { result.push(path); for (let i = start; i < nums.length; i++) { path.push(nums[i]); backtrack(i + 1, path); path.pop(); } } backtrack(0, []); return result; } console.log(subsets([1, 2]));

A SyntaxError due to missing semicolon

B No error, outputs correct subsets

C TypeError because path is undefined

D The output contains repeated references to the same array causing all subsets to be identical

💡 Hint

Look at how arrays are pushed into result and whether they are copied.

The code pushes the same array reference 'path' multiple times without copying it, so all entries in result point to the same array which changes over time.

🚀 Application

expert

Find subsets summing to target

Given the array [2, 3, 5, 7] and target sum 10, which subsets from the powerset sum exactly to 10?

A [[2,3,5,7]]

B [[5,7],[2,3,5]]

C [[3,7],[2,3,5]]

D [[2,7],[3,5]]

💡 Hint

Check sums of all subsets carefully.

Subsets [3,7] and [2,3,5] both sum to 10. Others do not.

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