Generate All Subsets Powerset in DSA Go

Mental Model

We find every possible group of items from a list, including empty and full groups.

Analogy: Imagine you have a box of 3 different colored balls. You want to see all ways you can pick some or none of them to play with.

Set: [A, B, C]
Subsets start empty: []
We add or skip each item to build all groups.

Dry Run Walkthrough

Input: list: [1, 2]

Goal: Find all subsets of [1, 2], including empty set and full set

Step 1: Start with empty subset []

[]

Why: We begin with no items selected

Step 2: Decide to skip 1, keep subset []

[]

Why: One choice is to not include the first item

Step 3: Decide to include 2, subset becomes [2]

[2]

Why: Add second item to current subset

Step 4: Backtrack to subset [], now include 1, subset becomes [1]

[1]

Why: Try including first item now

Step 5: Decide to skip 2, subset stays [1]

[1]

Why: Skip second item with first included

Step 6: Include 2, subset becomes [1, 2]

[1, 2]

Why: Include second item with first included

Result:

[]
[2]
[1]
[1 2]

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func generateSubsets(nums []int) [][]int {
	var result [][]int
	var subset []int

	var backtrack func(int)
	backtrack = func(index int) {
		if index == len(nums) {
			// Add a copy of current subset to result
			temp := make([]int, len(subset))
			copy(temp, subset)
			result = append(result, temp)
			return
		}

		// Skip current number
		backtrack(index + 1)

		// Include current number
		subset = append(subset, nums[index])
		backtrack(index + 1)

		// Backtrack: remove last number added
		subset = subset[:len(subset)-1]
	}

	backtrack(0)
	return result
}

func main() {
	nums := []int{1, 2}
	subsets := generateSubsets(nums)
	for _, s := range subsets {
		fmt.Println(s)
	}
}

if index == len(nums) {

Reached end of list, save current subset copy

backtrack(index + 1)

Skip current number and recurse

subset = append(subset, nums[index])

Include current number in subset

backtrack(index + 1)

Recurse after including current number

subset = subset[:len(subset)-1]

Remove last number to backtrack

Output

[]

[2]

[1]

[1 2]

Complexity Analysis

Time: O(2^n) because each element can be either included or excluded, doubling subsets each time

Space: O(n * 2^n) because we store all subsets and each subset can be up to size n

vs Alternative: Compared to iterative methods, backtracking is intuitive and easy to implement but both have similar exponential time

Edge Cases

empty list []

Returns [[]] because the only subset of empty set is empty set

DSA Go

if index == len(nums) {

single element list [5]

Returns [] and [5] as subsets

DSA Go

if index == len(nums) {

When to Use This Pattern

When asked to find all possible combinations or groups from a list, use backtracking to explore include/exclude choices for each item.

Common Mistakes

Mistake: Not making a copy of the current subset before adding to results
Fix: Create a new slice copy before appending to results to avoid mutation issues

Mistake: Not backtracking (removing last added element) after recursive call
Fix: Remove last element after recursion to restore subset state for next choices

Summary

Generates all possible subsets (powerset) of a given list.

Use when you need every combination of elements, including empty and full sets.

The key is to choose for each element whether to include it or not, exploring all paths.

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