Subsets Generation Using Bitmask in DSA Go - Execution Trace

Concept Flow - Subsets Generation Using Bitmask

Start with input set

↓

Calculate total subsets = 2^n

↓

For each number from 0 to 2^n - 1

↓

Use bits of number as mask

↓

Include elements where bit is 1

↓

Add formed subset to result

↓

Repeat until all subsets generated

↓

Return all subsets

We generate all subsets by counting from 0 to 2^n-1 and using each number's bits to decide which elements to include.

Execution Sample

DSA Go

input := []int{1, 2, 3}
for mask := 0; mask < (1 << len(input)); mask++ {
  subset := []int{}
  for i := 0; i < len(input); i++ {
    if mask&(1<<i) != 0 {
      subset = append(subset, input[i])
    }
  }
  fmt.Println(subset)
}

This code prints all subsets of [1, 2, 3] by using bitmask from 0 to 7.

Execution Table

Step	Mask (binary)	Subset Elements Included	Action	Subset Formed
1	000	None	No bits set, empty subset	[]
2	001	1	Bit 0 set, include input[0]	[1]
3	010	2	Bit 1 set, include input[1]	[2]
4	011	1, 2	Bits 0 and 1 set, include input[0], input[1]	[1, 2]
5	100	3	Bit 2 set, include input[2]	[3]
6	101	1, 3	Bits 0 and 2 set, include input[0], input[2]	[1, 3]
7	110	2, 3	Bits 1 and 2 set, include input[1], input[2]	[2, 3]
8	111	1, 2, 3	Bits 0, 1, 2 set, include all	[1, 2, 3]
9	-	-	All masks processed, subsets generated	Done

💡 Mask reached 2^3 = 8, all subsets generated

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
mask	0	0	1	2	3	4	5	6	7	8
subset	[]	[]	[1]	[2]	[1, 2]	[3]	[1, 3]	[2, 3]	[1, 2, 3]	[] (reset)
subset count	0	1	2	3	4	5	6	7	8	8

Key Moments - 3 Insights

Why do we use (1 << len(input)) as the upper limit for mask?

Because 1 << len(input) equals 2^n, which is the total number of subsets for a set of size n. The execution_table rows 1 to 8 show mask going from 0 to 7 (2^3 - 1).

How does the bitmask decide which elements to include in the subset?

Each bit in mask corresponds to an index in input. If bit i is 1, input[i] is included. This is shown in execution_table rows where bits set correspond to included elements.

Why is the subset reset to empty at each mask iteration?

Because each mask represents a new subset. We build it fresh by checking bits. variable_tracker shows subset resets after each step.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, which elements are included in the subset?

A Only element 3

B Elements 1 and 3

C Elements 2 and 3

D Elements 1 and 2

💡 Hint

Check the 'Subset Elements Included' column at Step 5 in execution_table

At which step does the mask first include elements 1 and 2 together?

A Step 3

B Step 4

C Step 6

D Step 7

💡 Hint

Look for mask with bits 0 and 1 set in execution_table

If the input had 4 elements, what would be the mask value for the subset including only the 4th element?

A 1 (0001)

B 8 (1000)

C 4 (0100)

D 15 (1111)

💡 Hint

The 4th element corresponds to bit index 3, so mask is 1 << 3 = 8

Concept Snapshot

Subsets Generation Using Bitmask:
- Total subsets = 2^n for n elements
- Iterate mask from 0 to 2^n - 1
- For each mask, include elements where bit is 1
- Each mask forms one unique subset
- Efficient way to generate all subsets

Full Transcript

We generate all subsets of a set by using a bitmask from 0 to 2^n - 1. Each bit in the mask represents whether to include the corresponding element. For example, mask 5 (binary 101) includes elements at positions 0 and 2. We reset the subset for each mask and build it by checking bits. This method ensures all subsets are covered without duplicates. The process stops after mask reaches 2^n, which is the total number of subsets.

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