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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of powerset generation with duplicates

What is the output of the following TypeScript code that generates all subsets (powerset) of an array with duplicates?

DSA Typescript

function subsets(nums: number[]): number[][] {
  const result: number[][] = [];
  nums.sort((a, b) => a - b);
  function backtrack(start: number, path: number[]) {
    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],[2],[1,2],[2,2],[1,2,2]]

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

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

D [[],[1],[1,2],[2],[2,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 uses backtracking to generate subsets. It skips duplicates by checking if the current number is the same as the previous one at the same recursion level. This ensures unique subsets only.

The output includes the empty subset, subsets with one element, and subsets with duplicates only once.

🧠 Conceptual

intermediate

Number of subsets in powerset

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

A 2^n

B n^2

C n

D n!

💡 Hint

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

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

🔧 Debug

advanced

Identify the bug in powerset generation

What error does the following TypeScript code produce when generating all subsets of [1,2]? function subsets(nums: number[]): number[][] { const result: number[][] = []; function backtrack(start: number, path: number[]) { 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 The output contains repeated references to the same array, causing all subsets to be the same at the end.

B SyntaxError due to missing colon in function parameter.

C TypeError because path is undefined inside backtrack.

D The output is correct with all subsets printed properly.

💡 Hint

Check how arrays are pushed into the result and if they are copied.

The code pushes the same array reference 'path' into the result multiple times. Since 'path' is mutated later, all entries in result point to the same final array state.

To fix, push a copy of 'path' using [...path].

❓ Predict Output

advanced

Output of iterative powerset generation

What is the output of the following TypeScript code that generates all subsets iteratively for input [1, 2]?

DSA Typescript

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]));

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

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

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

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

💡 Hint

The code starts with empty subset and adds each number to existing subsets.

The code starts with [[]]. For each number, it creates new subsets by adding the number to all existing subsets and appends them.

For [1,2], subsets are [], [1], [2], [1,2] in that order.

🧠 Conceptual

expert

Time complexity of generating all subsets

What is the time complexity of generating all subsets (powerset) of an array of length n?

A O(n!)

B O(2^n)

C O(n^2)

D O(n * 2^n)

💡 Hint

Consider the number of subsets and the cost to copy each subset.

There are 2^n subsets. Each subset can have up to n elements. Copying each subset takes O(n) time.

So total time is O(n * 2^n).

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