Generate All Subsets Powerset in DSA Go - Time & Space Complexity

Time Complexity: Generate All Subsets Powerset

O(n * 2^n)

Understanding Time Complexity

We want to understand how the time needed to generate all subsets grows as the input list gets bigger.

How does the number of operations change when we create every possible subset?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code builds all subsets by starting with an empty set and adding each number to existing subsets.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops where for each number, we loop over all existing subsets to create new ones.
• How many times: For each of the n numbers, we double the number of subsets by looping over all current subsets.

How Execution Grows With Input

Each new number doubles the subsets, so operations grow very fast.

Input Size (n)	Approx. Operations
10	About 2^10 = 1,024 subsets
20	About 2^20 = 1,048,576 subsets
30	About 2^30 = 1,073,741,824 subsets

Pattern observation: The number of subsets doubles with each added element, so the work grows exponentially.

Final Time Complexity

Time Complexity: O(n * 2^n)

This means the time grows very fast because for each of the n elements, we create twice as many subsets as before.

Common Mistake

[X] Wrong: "Generating all subsets is just O(n) because we loop over the input once."

[OK] Correct: Even though we loop over the input once, the number of subsets grows exponentially, so the total work is much larger than just n.

Interview Connect

Understanding this exponential growth helps you explain why some problems take much longer as input grows, showing your grasp of algorithm limits.

Self-Check

"What if we only wanted subsets of a fixed size k? How would the time complexity change?"

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