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).