Generate All Subsets Powerset in DSA Go - Build from Scratch

Generate All Subsets Powerset

📖 Scenario: Imagine you have a small collection of unique fruits. You want to find all possible combinations of these fruits, including the empty set and the full set. This is useful when you want to explore every possible selection you can make from your fruits.

🎯 Goal: Build a Go program that generates all subsets (the powerset) of a given list of fruits. The program will show each subset as a slice of strings.

📋 What You'll Learn

Create a slice of strings called fruits with the exact values: "apple", "banana", "cherry"

Create an empty slice of slice of strings called result to store all subsets

Write a recursive function called generateSubsets that takes the current index, the current subset, and appends all subsets to result

Call generateSubsets starting from index 0 with an empty current subset

Print the result slice showing all subsets

💡 Why This Matters

🌍 Real World

Generating all subsets is useful in scenarios like choosing combinations of items, feature selection in machine learning, and exploring all possible options in decision making.

💼 Career

Understanding recursion and powerset generation is important for software engineers working on algorithms, combinatorics problems, and optimization tasks.

1

Create the initial fruits slice

Create a slice of strings called fruits with these exact values: "apple", "banana", "cherry"

DSA Go

# Create the fruits slice with the exact values
# Your code here

Hint

Use fruits := []string{"apple", "banana", "cherry"} to create the slice.

2

Create the result slice to hold subsets

Add a variable called result as a slice of slice of strings to store all subsets. Initialize it as empty.

DSA Go

package main

func main() {
    fruits := []string{"apple", "banana", "cherry"}
    // Create an empty result slice to hold subsets
    // Your code here
}

Hint

Use var result [][]string to declare an empty slice of slices.

3

Write the recursive function to generate subsets

Write a recursive function called generateSubsets that takes these parameters: index int, current []string, fruits []string, and result *[][]string. The function should append a copy of current to *result. Then, if index is less than the length of fruits, recursively call itself twice: once without including fruits[index], and once including fruits[index] in current. Call this function from main starting with index 0 and empty current.

DSA Go

package main

func generateSubsets(index int, current []string, fruits []string, result *[][]string) {
    // Your code here
}

func main() {
    fruits := []string{"apple", "banana", "cherry"}
    var result [][]string
    // Call generateSubsets starting at index 0 with empty current slice
    // Your code here
}

Hint

Remember to append a copy of current to *result before recursing. Use append to add elements.

4

Print all subsets stored in result

Add a for loop in main to print each subset in result. Use fmt.Println(subset) to print each subset.

DSA Go

package main

import "fmt"

func generateSubsets(index int, current []string, fruits []string, result *[][]string) {
    subset := make([]string, len(current))
    copy(subset, current)
    *result = append(*result, subset)

    if index == len(fruits) {
        return
    }

    generateSubsets(index+1, current, fruits, result)

    generateSubsets(index+1, append(current, fruits[index]), fruits, result)
}

func main() {
    fruits := []string{"apple", "banana", "cherry"}
    var result [][]string
    generateSubsets(0, []string{}, fruits, &result)

    // Print all subsets in result
    // Your code here
}

Hint

Use a for loop with range over result and print each subset with fmt.Println(subset).

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