Subsets Generation Using Bitmask in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of subsets generated by bitmask

What is the output of the following Go code that generates all subsets of [1, 2] using bitmask?

DSA Go

package main
import "fmt"
func main() {
  nums := []int{1, 2}
  n := len(nums)
  for mask := 0; mask < (1 << n); mask++ {
    subset := []int{}
    for i := 0; i < n; i++ {
      if mask&(1<<i) != 0 {
        subset = append(subset, nums[i])
      }
    }
    fmt.Println(subset)
  }
}

A

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

B

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

C

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

D

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

💡 Hint

Think about how bitmask from 0 to 2^n - 1 represents subsets.

The code loops from 0 to 3 (2^2 - 1). Each bit in mask represents whether to include an element.

Mask 0 (00 binary) means no elements: []

Mask 1 (01 binary) means include first element: [1]

Mask 2 (10 binary) means include second element: [2]

Mask 3 (11 binary) means include both: [1 2]

🧠 Conceptual

intermediate

Number of subsets generated by bitmask

If you have a set of 5 elements, how many subsets will the bitmask method generate?

A 64

B 25

C 10

D 32

💡 Hint

Number of subsets of a set with n elements is 2^n.

Each element can be either included or excluded, so total subsets = 2^n.

For n=5, total subsets = 2^5 = 32.

🔧 Debug

advanced

Identify the error in subset generation code

What error does the following Go code produce when generating subsets using bitmask?

DSA Go

package main
import "fmt"
func main() {
  nums := []int{1, 2, 3}
  n := len(nums)
  for mask := 0; mask <= (1 << n); mask++ {
    subset := []int{}
    for i := 0; i < n; i++ {
      if mask&(1<<i) != 0 {
        subset = append(subset, nums[i])
      }
    }
    fmt.Println(subset)
  }
}

A Runtime panic: index out of range

B Runs correctly and prints all subsets

C Infinite loop

D Compilation error: invalid syntax

💡 Hint

Check the loop condition for mask and the range of mask values.

The loop runs mask from 0 to 8 inclusive (since n=3, 1<<3=8).

But valid masks are from 0 to 7 (0 to 2^3 - 1).

When mask=8, the inner loop tries to access nums[3], which is out of range.

🚀 Application

advanced

Find subsets with sum equal to target using bitmask

Given nums = [2, 4, 6, 8] and target = 10, which subsets will the bitmask method print that sum to the target?

DSA Go

package main
import "fmt"
func main() {
  nums := []int{2, 4, 6, 8}
  target := 10
  n := len(nums)
  for mask := 0; mask < (1 << n); mask++ {
    subset := []int{}
    sum := 0
    for i := 0; i < n; i++ {
      if mask&(1<<i) != 0 {
        subset = append(subset, nums[i])
        sum += nums[i]
      }
    }
    if sum == target {
      fmt.Println(subset)
    }
  }
}

A

[2 4]
[6 8]

B [6 8]

C

[4 6]
[2 8]

D

[2 4 6]
[8]

💡 Hint

Check which combinations of numbers add up to 10.

Subsets that sum to 10 are [4, 6] and [2, 8].

Other subsets do not sum to 10.

🧠 Conceptual

expert

Time complexity of subsets generation using bitmask

What is the time complexity of generating all subsets of a set of size n using the bitmask method?

A O(2^n)

B O(n * 2^n)

C O(n^2)

D O(n!)

💡 Hint

Consider how many subsets and how many elements per subset are processed.

There are 2^n subsets.

For each subset, we check up to n elements.

So total time is O(n * 2^n).

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