Generate All Subsets Powerset in DSA Typescript - Execution Trace

Concept Flow - Generate All Subsets Powerset

Start with empty subset

↓

Pick next element?

No→Add current subset to result

Yes↓

Include element in subset

→Recurse

↓

Exclude element from subset

→Recurse

↓

Backtrack to previous element

We start with an empty subset and for each element, choose to include or exclude it, recursively building all subsets until all elements are processed.

Execution Sample

DSA Typescript

function generateSubsets(nums: number[]): number[][] {
  const result: number[][] = [];
  function backtrack(index: number, subset: number[]) {
    if (index === nums.length) {
      result.push([...subset]);
      return;
    }
    subset.push(nums[index]);
    backtrack(index + 1, subset);
    subset.pop();
    backtrack(index + 1, subset);
  }
  backtrack(0, []);
  return result;
}

This code recursively builds all subsets by including or excluding each element, collecting all subsets in result.

Execution Table

Step	Operation	Current Index	Current Subset	Action	Resulting Subsets
1	Start recursion	0	[]	Start with empty subset	[]
2	Include nums[0]=1	0	[]	Add 1 to subset	[]
3	Recurse with index=1	1	[1]	Include nums[1]=2	[]
4	Include nums[1]=2	1	[1]	Add 2 to subset	[]
5	Recurse with index=2	2	[1,2]	Include nums[2]=3	[]
6	Include nums[2]=3	2	[1,2]	Add 3 to subset	[]
7	Recurse with index=3	3	[1,2,3]	Index == length, add subset	[[1,2,3]]
8	Backtrack	2	[1,2,3]	Remove 3 from subset	[[1,2,3]]
9	Exclude nums[2]=3	2	[1,2]	Do not add 3	[[1,2,3]]
10	Recurse with index=3	3	[1,2]	Index == length, add subset	[[1,2,3],[1,2]]
11	Backtrack	1	[1,2]	Remove 2 from subset	[[1,2,3],[1,2]]
12	Exclude nums[1]=2	1	[1]	Do not add 2	[[1,2,3],[1,2]]
13	Recurse with index=2	2	[1]	Include nums[2]=3	[[1,2,3],[1,2]]
14	Include nums[2]=3	2	[1]	Add 3 to subset	[[1,2,3],[1,2]]
15	Recurse with index=3	3	[1,3]	Index == length, add subset	[[1,2,3],[1,2],[1,3]]
16	Backtrack	2	[1,3]	Remove 3 from subset	[[1,2,3],[1,2],[1,3]]
17	Exclude nums[2]=3	2	[1]	Do not add 3	[[1,2,3],[1,2],[1,3]]
18	Recurse with index=3	3	[1]	Index == length, add subset	[[1,2,3],[1,2],[1,3],[1]]
19	Backtrack	0	[1]	Remove 1 from subset	[[1,2,3],[1,2],[1,3],[1]]
20	Exclude nums[0]=1	0	[]	Do not add 1	[[1,2,3],[1,2],[1,3],[1]]
21	Recurse with index=1	1	[]	Include nums[1]=2	[[1,2,3],[1,2],[1,3],[1]]
22	Include nums[1]=2	1	[]	Add 2 to subset	[[1,2,3],[1,2],[1,3],[1]]
23	Recurse with index=2	2	[2]	Include nums[2]=3	[[1,2,3],[1,2],[1,3],[1]]
24	Include nums[2]=3	2	[2]	Add 3 to subset	[[1,2,3],[1,2],[1,3],[1]]
25	Recurse with index=3	3	[2,3]	Index == length, add subset	[[1,2,3],[1,2],[1,3],[1],[2,3]]
26	Backtrack	2	[2,3]	Remove 3 from subset	[[1,2,3],[1,2],[1,3],[1],[2,3]]
27	Exclude nums[2]=3	2	[2]	Do not add 3	[[1,2,3],[1,2],[1,3],[1],[2,3]]
28	Recurse with index=3	3	[2]	Index == length, add subset	[[1,2,3],[1,2],[1,3],[1],[2,3],[2]]
29	Backtrack	1	[2]	Remove 2 from subset	[[1,2,3],[1,2],[1,3],[1],[2,3],[2]]
30	Exclude nums[1]=2	1	[]	Do not add 2	[[1,2,3],[1,2],[1,3],[1],[2,3],[2]]
31	Recurse with index=2	2	[]	Include nums[2]=3	[[1,2,3],[1,2],[1,3],[1],[2,3],[2]]
32	Include nums[2]=3	2	[]	Add 3 to subset	[[1,2,3],[1,2],[1,3],[1],[2,3],[2]]
33	Recurse with index=3	3	[3]	Index == length, add subset	[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3]]
34	Backtrack	2	[3]	Remove 3 from subset	[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3]]
35	Exclude nums[2]=3	2	[]	Do not add 3	[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3]]
36	Recurse with index=3	3	[]	Index == length, add subset	[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
37	End recursion	3	[]	All subsets generated	[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

💡 Recursion ends when index reaches length of input array, all subsets collected.

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 10	After Step 18	After Step 26	After Step 36	Final
index	0	1	3	3	3	3	3	3
subset	[]	[1]	[1,2,3]	[1,2]	[1]	[2]	[]	[]
result length	0	0	0	2	4	5	8	8

Key Moments - 3 Insights

Why do we add the subset to result only when index equals the array length?

Because at that point, we have made decisions for all elements, so the current subset is complete. See steps 7, 10, 15, 18, 25, 28, 33, 36 in execution_table.

Why do we push and then pop elements in the subset during recursion?

Pushing adds the current element to the subset for the 'include' branch, and popping removes it to backtrack before exploring the 'exclude' branch. This ensures subsets are built correctly without leftover elements. See steps 2-3 and 6-8.

Why does the final result contain subsets in this order?

Because the recursion explores including elements first, then excluding, leading to subsets ordered by inclusion decisions. The order matches the sequence in the Resulting Subsets column.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what subset is added to the result?

A [1, 2]

B [1, 2, 3]

C [1, 3]

D [2, 3]

💡 Hint

Check the 'Current Subset' and 'Resulting Subsets' columns at step 7.

At which step does the recursion first exclude the element nums[2]=3?

A Step 17

B Step 10

C Step 9

D Step 18

💡 Hint

Look for the first 'Exclude nums[2]=3' action in the Action column.

If we change the input array to [1, 2], how many subsets will the final result contain?

A 4

B 3

C 2

D 8

💡 Hint

Number of subsets is 2^n, where n is the length of the input array. Check variable_tracker for result length.

Concept Snapshot

Generate All Subsets (Powerset):
- Use recursion with backtracking
- At each index, choose to include or exclude element
- When index == array length, add current subset to result
- Backtrack by removing last element before excluding
- Total subsets = 2^n for n elements
- Result contains all possible subsets

Full Transcript

This visualization shows how to generate all subsets (powerset) of an array using recursion and backtracking. We start with an empty subset and at each step decide to include or exclude the current element. When we reach the end of the array, we add the current subset to the result. We use push and pop to manage the subset during recursion. The execution table tracks each step, showing the current index, subset, action, and subsets collected so far. The variable tracker shows how index, subset, and result length change over time. Key moments clarify why subsets are added only at the end and why backtracking is needed. The quiz tests understanding of subset addition, exclusion steps, and subset count for smaller inputs.

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