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.