Subsets Generation Using Bitmask in DSA Go - Build from Scratch

Subsets Generation Using Bitmask

📖 Scenario: Imagine you have a small collection of fruits and you want to find all possible groups (subsets) you can make from them. This is useful when you want to explore every combination, like choosing fruits for a fruit salad.

🎯 Goal: You will write a Go program that uses bitmasking to generate all subsets of a given list of fruits.

📋 What You'll Learn

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

Create an integer variable called n that stores the length of fruits

Use a for loop with variable mask from 0 to (1 << n) - 1 to generate subsets

Inside the loop, use another for loop with variable i from 0 to n - 1 to check bits in mask

Print each subset as a slice of strings

💡 Why This Matters

🌍 Real World

Generating subsets is useful in many real-world problems like choosing combinations of items, testing all possible feature sets in machine learning, or exploring options in decision making.

💼 Career

Understanding subsets and bitmasking is important for software engineers working on algorithms, optimization problems, and coding interviews.

1

Create the fruits slice

Create a slice of strings called fruits with the 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 length variable

Create an integer variable called n that stores the length of fruits using len(fruits)

DSA Go

package main

import "fmt"

func main() {
    fruits := []string{"apple", "banana", "cherry"}
    // Create variable n to store length of fruits
    // Your code here
}

Hint

Use n := len(fruits) to get the number of fruits.

3

Generate subsets using bitmask

Use a for loop with variable mask from 0 to (1 << n) - 1 to generate subsets. Inside it, use another for loop with variable i from 0 to n - 1 to check if the i-th bit in mask is set. If set, append fruits[i] to a slice called subset.

DSA Go

package main

import "fmt"

func main() {
    fruits := []string{"apple", "banana", "cherry"}
    n := len(fruits)

    // Generate subsets using bitmask
    // Your code here
}

Hint

Use bitwise AND mask & (1 << i) to check if bit i is set.

4

Print each subset

Print each subset slice inside the outer for loop using fmt.Println(subset)

DSA Go

package main

import "fmt"

func main() {
    fruits := []string{"apple", "banana", "cherry"}
    n := len(fruits)

    for mask := 0; mask < (1 << n); mask++ {
        subset := []string{}
        for i := 0; i < n; i++ {
            if mask&(1<<i) != 0 {
                subset = append(subset, fruits[i])
            }
        }
        // Print the subset
        // Your code here
    }
}

Hint

Use fmt.Println(subset) to print each subset.

Practice

1. What does the bitmask technique help generate when applied to a set of elements?

easy

A. Only subsets with odd number of elements

B. Only the largest subset

C. All possible subsets of the set

D. Only subsets with even number of elements

Solution

1. Step 1: Understand bitmask representation

   Each bit in the bitmask represents whether an element is included (1) or excluded (0) in a subset.

2. Step 2: Generate subsets using all bitmasks

   By iterating from 0 to 2^n - 1, all combinations of included/excluded elements are covered, producing all subsets.

3. Final Answer:

   All possible subsets of the set -> Option C

4. Quick Check:

   Bitmask = subsets generator [OK]

Hint: Bitmask bits map directly to subset inclusion [OK]

Common Mistakes:

• Thinking bitmask generates only specific subsets
• Confusing bitmask with sorting or filtering
• Ignoring subsets with zero elements

2. Which of the following is the correct Go syntax to iterate over all bitmasks for a set of size n?

easy

A. for mask := 0; mask < n; mask++ { }"

B. for mask := 1; mask <= n; mask++ { }"

C. for mask := 0; mask <= n; mask++ { }"

D. for mask := 0; mask < (1 << n); mask++ { }"

Solution

1. Step 1: Understand bitmask range

   For n elements, bitmasks range from 0 to 2^n - 1, which is (1 << n) - 1.

2. Step 2: Correct loop condition

   The loop must run from 0 up to but not including (1 << n), so mask < (1 << n) is correct.

3. Final Answer:

   for mask := 0; mask < (1 << n); mask++ { } -> Option D

4. Quick Check:

   Loop runs 0 to 2^n-1 [OK]

Hint: Use mask < (1 << n) for full bitmask range [OK]

Common Mistakes:

• Using mask <= n instead of mask < (1 << n)
• Starting mask from 1 misses empty subset
• Using mask < n only iterates n times, not 2^n

3. What is the output subsets generated by the following Go code snippet?

arr := []int{1, 2}
for mask := 0; mask < (1 << 2); mask++ {
  subset := []int{}
  for i := 0; i < 2; i++ {
    if mask&(1<

medium

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

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

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

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

Solution

1. Step 1: Understand bitmask values

   For n=2, masks go 0 to 3: 0 (00), 1 (01), 2 (10), 3 (11).

2. Step 2: Map bits to subsets

   Mask 0: no bits set -> [] Mask 1: bit 0 set -> [1] Mask 2: bit 1 set -> [2] Mask 3: bits 0 and 1 set -> [1, 2]

3. Final Answer:

   [ ] [1] [2] [1 2] -> Option A

4. Quick Check:

   Bitmask order matches subsets [OK]

Hint: Map bits to elements in order from least significant bit [OK]

Common Mistakes:

• Mixing order of subsets printed
• Confusing which bit corresponds to which element
• Missing empty subset when mask=0

4. Identify the error in this Go code snippet for generating subsets using bitmask:

arr := []int{1, 2, 3}
for mask := 0; mask <= (1 << len(arr)); mask++ {
  subset := []int{}
  for i := 0; i < len(arr); i++ {
    if mask&(1<

medium

A. Loop condition should be mask < (1 << len(arr))

B. Bitwise AND operator should be | instead of &

C. Inner loop should run from i = 1 to len(arr)

D. Array indexing should start from 1 instead of 0

Solution

1. Step 1: Analyze loop condition

   The outer loop runs mask from 0 to (1 << n) inclusive, which is one too many iterations (2^n + 1).

2. Step 2: Correct loop range

   It should run from 0 up to but not including (1 << n), so mask < (1 << n) is correct to avoid out-of-range subsets.

3. Final Answer:

   Loop condition should be mask < (1 << len(arr)) -> Option A

4. Quick Check:

   Loop must run 2^n times exactly [OK]

Hint: Use <, not <=, for bitmask loop upper bound [OK]

Common Mistakes:

• Using <= causes one extra invalid iteration
• Confusing & with | for bit checking
• Changing loop indices incorrectly

5. Given a set arr := []int{1, 2, 3, 4}, how many subsets generated by bitmask will have exactly 2 elements?

hard

A. 4

B. 6

C. 8

D. 12

Solution

1. Step 1: Understand subsets count by size

   Number of subsets of size k from n elements is combination n choose k = C(n, k).

2. Step 2: Calculate C(4, 2)

   C(4, 2) = 4! / (2! * (4-2)!) = (4*3)/(2*1) = 6.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Number of 2-element subsets = 6 [OK]

Hint: Use combinations formula C(n, k) for subset sizes [OK]

Common Mistakes:

• Counting all subsets instead of only size 2
• Using permutations instead of combinations
• Misapplying formula for combinations