Subsets Generation Using Bitmask in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to generate all subsets of nums using bitmask.

DSA Go

for mask := 0; mask < (1 << [1]); mask++ {
    subset := []int{}
    for i := 0; i < len(nums); i++ {
        if mask&(1<<i) != 0 {
            subset = append(subset, nums[i])
        }
    }
    result = append(result, subset)
}

Drag options to blanks, or click blank then click option'

Alen(nums)

Bcap(nums)

Cnums[0]

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using cap(nums) instead of len(nums)

Using a fixed number instead of length

Using nums[0] which is a value, not length

We use len(nums) to know how many bits we need to represent all subsets.

2fill in blank

medium

Complete the code to check if the i-th bit is set in mask.

DSA Go

if mask & ([1] << i) != 0 {
    subset = append(subset, nums[i])
}

Drag options to blanks, or click blank then click option'

Amask

B0

C1

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using mask instead of 1 for shifting

Using i without shifting

Using 0 which always results in zero

We shift 1 by i to check if the i-th bit in mask is set.

3fill in blank

hard

Fix the error in the code to append subsets correctly.

DSA Go

result = append(result, [1])

Drag options to blanks, or click blank then click option'

Anums[i]

Bsubset

Cmask

Dnums

Attempts:

3 left

💡 Hint

Common Mistakes

Appending nums[i] instead of subset

Appending mask which is an integer

Appending the entire nums slice every time

We append the current subset slice, not a single element or mask.

4fill in blank

hard

Fill both blanks to create a map of subset sums and their counts.

DSA Go

sumCount := map[int]int{}
for mask := 0; mask < (1 << [1]); mask++ {
    sum := 0
    for i := 0; i < [2]; i++ {
        if mask&(1<<i) != 0 {
            sum += nums[i]
        }
    }
    sumCount[sum]++
}

Drag options to blanks, or click blank then click option'

Alen(nums)

Bcap(nums)

Clen(nums) - 1

Dlen(result)

Attempts:

3 left

💡 Hint

Common Mistakes

Using cap(nums) which may differ from length

Using len(nums) - 1 which misses last element

Using len(result) which is unrelated

Both blanks use len(nums) to iterate over all elements correctly.

5fill in blank

hard

Fill all three blanks to create a map of subsets keyed by their bitmask.

DSA Go

subsetMap := map[int][]int{}
for [1] := 0; [2] < (1 << len(nums)); [2]++ {
    subset := []int{}
    for i := 0; i < len(nums); i++ {
        if [2]&(1<<i) != 0 {
            subset = append(subset, nums[i])
        }
    }
    subsetMap[[2]] = subset
}

Drag options to blanks, or click blank then click option'

Amask

Ci

Dcount

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names for loop and map key

Using i as loop variable in outer loop

Using count which is undefined

The loop variable is mask, used consistently to track subsets and keys.

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