Generate All Subsets Powerset in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of powerset generation with duplicates

What is the output of this Go code that generates all subsets (powerset) of the slice [1, 2]?

DSA Go

package main
import "fmt"
func subsets(nums []int) [][]int {
    res := [][]int{{}}
    for _, num := range nums {
        n := len(res)
        for i := 0; i < n; i++ {
            subset := append([]int{}, res[i]...)
            subset = append(subset, num)
            res = append(res, subset)
        }
    }
    return res
}
func main() {
    result := subsets([]int{1, 2})
    fmt.Println(result)
}

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

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

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

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

💡 Hint

Think about how subsets are built by adding each number to existing subsets.

The code starts with an empty subset and for each number, it adds that number to all existing subsets, doubling the number of subsets each time. The order of subsets is preserved as shown in option C.

❓ Predict Output

intermediate

Output of recursive powerset function

What is the output of this recursive Go function generating all subsets of [3]?

DSA Go

package main
import "fmt"
func subsets(nums []int) [][]int {
    if len(nums) == 0 {
        return [][]int{{}}
    }
    first := nums[0]
    rest := subsets(nums[1:])
    newSubsets := [][]int{}
    for _, subset := range rest {
        newSubset := append([]int{first}, subset...)
        newSubsets = append(newSubsets, newSubset)
    }
    return append(rest, newSubsets...)
}
func main() {
    result := subsets([]int{3})
    fmt.Println(result)
}

A [[], [3]]

B [[3], []]

C [[3]]

D [[]]

💡 Hint

Base case returns empty subset; recursive step adds first element to all subsets.

The function returns the empty subset first, then adds the first element to each subset, resulting in [[], [3]].

🔧 Debug

advanced

Identify the error in powerset generation code

What error does this Go code produce when generating subsets of [1, 2]?

DSA Go

package main
import "fmt"
func subsets(nums []int) [][]int {
    res := [][]int{{}}
    for _, num := range nums {
        for _, subset := range res {
            subset = append(subset, num)
            res = append(res, subset)
        }
    }
    return res
}
func main() {
    result := subsets([]int{1, 2})
    fmt.Println(result)
}

A Infinite loop

B Output includes repeated elements in subsets

C Runtime error: concurrent slice modification

D Compilation error: cannot append to range variable

💡 Hint

Appending to subsets inside the loop modifies the slice being iterated over.

Appending to `res` while iterating over it with `range` causes an infinite loop because `len(res)` is re-evaluated each iteration and keeps increasing.

❓ Predict Output

advanced

Output of powerset with empty input slice

What is the output of this Go code generating all subsets of an empty slice?

DSA Go

package main
import "fmt"
func subsets(nums []int) [][]int {
    res := [][]int{{}}
    for _, num := range nums {
        n := len(res)
        for i := 0; i < n; i++ {
            subset := append([]int{}, res[i]...)
            subset = append(subset, num)
            res = append(res, subset)
        }
    }
    return res
}
func main() {
    result := subsets([]int{})
    fmt.Println(result)
}

A nil

B []

C [[], []]

D [[]]

💡 Hint

The powerset of empty set contains one subset: the empty set itself.

The function initializes res with [[]], so the output is a slice containing one empty slice.

🧠 Conceptual

expert

Number of subsets generated by powerset function

If the input slice has length n, how many subsets does the powerset function generate?

A n

B 2^n

C n^2

D n!

💡 Hint

Each element can either be in or out of a subset.

Each element has two choices: included or excluded, so total subsets are 2^n.

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