Generate All Subsets Powerset in DSA Go - 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 state

↩Back to Pick next element?

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

Execution Sample

DSA Go

func generateSubsets(nums []int, index int, current []int, result *[][]int) {
    if index == len(nums) {
        *result = append(*result, append([]int{}, current...))
        return
    }
    generateSubsets(nums, index+1, current, result)
    generateSubsets(nums, index+1, append(current, nums[index]), result)
}

This Go function recursively generates all subsets of nums by including or excluding each element.

Execution Table

Step	Operation	Index	Current Subset	Action	Resulting Subsets
1	Start	0	[]	Check index == len(nums)? No	[]
2	Exclude nums[0]	1	[]	Recurse without nums[0]	[]
3	Exclude nums[1]	2	[]	Recurse without nums[1]	[]
4	Exclude nums[2]	3	[]	Index == len(nums), add []	[[]]
5	Include nums[2]	3	[3]	Index == len(nums), add [3]	[[], [3]]
6	Back to index 2	2	[]	Include nums[1]	Recurse with [2]
7	Exclude nums[2]	3	[2]	Index == len(nums), add [2]	[[], [3], [2]]
8	Include nums[2]	3	[2,3]	Index == len(nums), add [2,3]	[[], [3], [2], [2,3]]
9	Back to index 1	1	[]	Include nums[0]	Recurse with [1]
10	Exclude nums[1]	2	[1]	Recurse without nums[1]	[[], [3], [2], [2,3]]
11	Exclude nums[2]	3	[1]	Index == len(nums), add [1]	[[], [3], [2], [2,3], [1]]
12	Include nums[2]	3	[1,3]	Index == len(nums), add [1,3]	[[], [3], [2], [2,3], [1], [1,3]]
13	Back to index 2	2	[1]	Include nums[1]	Recurse with [1,2]
14	Exclude nums[2]	3	[1,2]	Index == len(nums), add [1,2]	[[], [3], [2], [2,3], [1], [1,3], [1,2]]
15	Include nums[2]	3	[1,2,3]	Index == len(nums), add [1,2,3]	[[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]
16	End	0	[]	All subsets generated	[[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]

💡 All elements processed, all subsets generated.

Variable Tracker

Variable	Start	After Step 4	After Step 8	After Step 12	After Step 15	Final
index	0	3	3	3	3	0 (end)
current subset	[]	[]	[2,3]	[1,3]	[1,2,3]	[]
resulting subsets	[]	[[]]	[[], [3], [2], [2,3]]	[[], [3], [2], [2,3], [1], [1,3]]	[[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]	[[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]

Key Moments - 3 Insights

Why do we add the current subset to the result only when index == len(nums)?

Because at that point, we have decided for every element whether to include or exclude it, so the current subset is complete (see steps 4,5,7,8,11,12,14,15).

Why do we recurse twice at each step?

One recursion excludes the current element, the other includes it, ensuring all combinations are explored (see steps 2 and 3, 6 and 7, 10 and 11, 13 and 14).

Why do we append a copy of current subset instead of current directly?

Because current is modified during recursion, appending a copy preserves the subset state at that moment (see code line with append([]int{}, current...)).

Visual Quiz - 3 Questions

Look at the execution table at step 8, what subsets have been added to the result?

A [[], [3], [2], [2,3]]

B [[], [3], [2]]

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

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

💡 Hint

Check the 'Resulting Subsets' column at step 8 in the execution_table.

At which step does the subset [1,3] get added to the result?

A Step 11

B Step 12

C Step 14

D Step 15

💡 Hint

Look for the 'Action' column mentioning adding [1,3] in the execution_table.

If we change the order of recursion to include element first, then exclude, how would the subsets order change?

A Subsets would be generated in reverse order

B Subsets order would remain the same

C Only subsets with first element included would appear

D Subsets would be duplicated

💡 Hint

Consider the recursion calls order in the execution_table and how changing it affects subset generation order.

Concept Snapshot

Generate All Subsets (Powerset):
- Use recursion with index and current subset
- At each step, recurse twice: exclude or include current element
- When index == len(nums), add a copy of current subset to result
- Result contains all 2^n subsets
- Backtracking ensures all combinations are explored

Full Transcript

This visualization shows how to generate all subsets of a list using recursion. We start with an empty subset and at each element, we decide to include or exclude it. This creates two recursive calls per element. When we reach the end of the list, we add the current subset to the result. The execution table traces each step, showing the current index, subset, and subsets collected so far. The variable tracker shows how index, current subset, and result change over time. Key moments clarify why subsets are added only at the end and why we copy the current subset. The quiz tests understanding of subset addition steps and recursion order effects.

Practice

1. What does the term powerset mean in the context of sets?

easy

A. The set of elements repeated twice

B. All possible subsets of a given set including empty and full set

C. The set itself without any subsets

D. Only the subsets with exactly two elements

Solution

1. Step 1: Understand the definition of powerset

   The powerset of a set is the collection of all possible 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 the powerset as all subsets. Other options describe partial or incorrect concepts.

3. Final Answer:

   All possible subsets of a given set including empty and full set -> Option B

4. Quick Check:

   powerset = all subsets [OK]

Hint: Powerset means every subset possible [OK]

Common Mistakes:

• Thinking powerset excludes empty set
• Confusing powerset with subsets of fixed size
• Assuming powerset duplicates elements

2. Which of the following Go code snippets correctly initializes an empty slice of slices of integers to store subsets?

easy

A. var subsets [][]int = []int{}

B. var subsets []int = []int{}

C. var subsets []int = [][]int{}

D. var subsets [][]int = [][]int{}

Solution

1. Step 1: Identify the type for storing subsets

   Subsets are slices of integers, so a slice of slices of int is needed: [][]int.

2. Step 2: Check initialization syntax

   var subsets [][]int = [][]int{} correctly initializes an empty slice of slices of int. Other options mismatch types.

3. Final Answer:

   var subsets [][]int = [][]int{} -> Option D

4. Quick Check:

   Correct slice of slices initialization [OK]

Hint: Use [][]int for slice of int slices [OK]

Common Mistakes:

• Using []int instead of [][]int for subsets
• Mixing types in initialization
• Incorrect empty slice syntax

3. What is the output of the following Go code that generates all subsets of []int{1, 2}?

func subsets(nums []int) [][]int {
    res := [][]int{{}}
    for _, num := range nums {
        newSubsets := [][]int{}
        for _, subset := range res {
            newSubset := append([]int{}, subset...)
            newSubset = append(newSubset, num)
            newSubsets = append(newSubsets, newSubset)
        }
        res = append(res, newSubsets...)
    }
    return res
}

func main() {
    result := subsets([]int{1, 2})
    fmt.Println(result)
}

medium

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

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

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

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

Solution

1. Step 1: Trace initial state and first iteration

   Start with res = [[]]. For num=1, add subsets [1], so res = [[], [1]].

2. Step 2: Trace second iteration

   For num=2, add subsets [2] and [1,2], so res = [[], [1], [2], [1, 2]].

3. Final Answer:

   [[], [1], [2], [1, 2]] -> Option C

4. Quick Check:

   All subsets of {1,2} listed [OK]

Hint: Start with empty subset, add each number to existing subsets [OK]

Common Mistakes:

• Missing empty subset in result
• Not appending new subsets correctly
• Confusing order of subsets

4. The following Go code attempts to generate all subsets of []int{1, 2}. What is the bug?

func subsets(nums []int) [][]int {
    res := [][]int{{}}
    for _, num := range nums {
        for i := range res {
            res[i] = append(res[i], num)
            res = append(res, [][]int{res[i]})
        }
    }
    return res
}

medium

A. Appending to res[i] modifies original subsets causing duplicates

B. res is not initialized properly

C. Loop variable num is not used

D. Function returns nil instead of subsets

Solution

1. Step 1: Understand slice append behavior in loop

   Appending to res[i] modifies the original slice in res because slices share underlying arrays.

2. Step 2: Identify consequence of modifying original subsets

   This causes all subsets to be changed and duplicates appear, breaking correct subset generation.

3. Final Answer:

   Appending to res[i] modifies original subsets causing duplicates -> Option A

4. Quick Check:

   Modify copy, not original slice [OK]

Hint: Copy slice before append to avoid modifying original [OK]

Common Mistakes:

• Appending directly to loop variable slice
• Not creating new slice copy
• Ignoring slice reference behavior

5. Given a set []int{1, 2, 2} with duplicate elements, which approach correctly generates all unique subsets (powerset without duplicates)?

hard

A. Sort input, then use backtracking skipping duplicates when choosing elements

B. Use a map to store subsets as keys without sorting input

C. Generate all subsets and then remove duplicates by comparing slices

D. Ignore duplicates and generate subsets normally

Solution

1. Step 1: Understand duplicate handling in subsets

   Duplicates cause repeated subsets if not handled carefully.

2. Step 2: Use sorting and skip duplicates during backtracking

   Sorting input helps detect duplicates. Skipping duplicates when choosing elements avoids repeated subsets efficiently.

3. Final Answer:

   Sort input, then use backtracking skipping duplicates when choosing elements -> Option A

4. Quick Check:

   Sort + skip duplicates = unique subsets [OK]

Hint: Sort input and skip duplicates during recursion [OK]

Common Mistakes:

• Not sorting input before backtracking
• Removing duplicates after generation (inefficient)
• Ignoring duplicates causing repeated subsets