Subsets Generation Using Bitmask in DSA Go

Mental Model

We use numbers in binary form to represent which elements to include in a subset. Each bit tells us if an element is in or out.

Analogy: Imagine a row of light switches, each switch controls one item. On means include the item, off means exclude it. By flipping switches in all possible ways, we get all subsets.

Set: [a, b, c]
Bitmask: 000 -> []
         001 -> [a]
         010 -> [b]
         011 -> [a, b]
         100 -> [c]
         101 -> [a, c]
         110 -> [b, c]
         111 -> [a, b, c]

Dry Run Walkthrough

Input: set: [1, 2, 3]

Goal: Generate all subsets of [1, 2, 3] using bitmask

Step 1: Start with bitmask 000 (0 in decimal), no elements included

bitmask=000 -> subset=[]

Why: This represents the empty subset

Step 2: Bitmask 001 (1 decimal), include element at index 0

bitmask=001 -> subset=[1]

Why: Bit 0 is on, so include first element

Step 3: Bitmask 010 (2 decimal), include element at index 1

bitmask=010 -> subset=[2]

Why: Bit 1 is on, so include second element

Step 4: Bitmask 011 (3 decimal), include elements at index 0 and 1

bitmask=011 -> subset=[1, 2]

Why: Bits 0 and 1 are on, include first two elements

Step 5: Bitmask 100 (4 decimal), include element at index 2

bitmask=100 -> subset=[3]

Why: Bit 2 is on, include third element

Step 6: Bitmask 101 (5 decimal), include elements at index 0 and 2

bitmask=101 -> subset=[1, 3]

Why: Bits 0 and 2 are on, include first and third elements

Step 7: Bitmask 110 (6 decimal), include elements at index 1 and 2

bitmask=110 -> subset=[2, 3]

Why: Bits 1 and 2 are on, include second and third elements

Step 8: Bitmask 111 (7 decimal), include all elements

bitmask=111 -> subset=[1, 2, 3]

Why: All bits on, include all elements

Result:

All subsets: []
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

Annotated Code

DSA Go

package main

import "fmt"

func subsets(nums []int) [][]int {
    n := len(nums)
    total := 1 << n // total subsets = 2^n
    result := [][]int{}

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

func main() {
    nums := []int{1, 2, 3}
    res := subsets(nums)
    for _, subset := range res {
        fmt.Println(subset)
    }
}

total := 1 << n // total subsets = 2^n

Calculate total number of subsets as 2 to the power of n

for bitmask := 0; bitmask < total; bitmask++ {

Iterate over all bitmasks from 0 to 2^n - 1

if bitmask&(1<<i) != 0 {

Check if bit i is set in bitmask to decide inclusion

subset = append(subset, nums[i])

Include element nums[i] in current subset

result = append(result, subset)

Add current subset to result list

Output

[]

[1]

[2]

[1 2]

[3]

[1 3]

[2 3]

[1 2 3]

Complexity Analysis

Time: O(n * 2^n) because we generate 2^n subsets and check n bits for each

Space: O(n * 2^n) because we store all subsets, each up to size n

vs Alternative: Compared to recursive backtracking, bitmask is iterative and often simpler to implement but both have same time complexity

Edge Cases

empty input list

returns one subset: the empty subset []

DSA Go

total := 1 << n // total subsets = 2^n

single element list

returns two subsets: [] and [element]

DSA Go

for bitmask := 0; bitmask < total; bitmask++ {

When to Use This Pattern

When asked to generate all subsets or combinations of a set, especially with small input size, use bitmask to represent inclusion/exclusion efficiently.

Common Mistakes

Mistake: Not using bit shifts correctly to check bits in bitmask
Fix: Use (bitmask & (1 << i)) != 0 to check if bit i is set

Mistake: Forgetting to generate all bitmasks from 0 to 2^n - 1
Fix: Loop bitmask from 0 up to (1 << n) - 1 inclusive

Summary

Generates all subsets of a set by using binary numbers to represent which elements to include.

Use when you need to list all possible combinations or subsets of a small set.

Each bit in a number acts like a switch to include or exclude an element, making subset generation simple and systematic.

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