Subsets Generation Using Bitmask in DSA Java - Execution Trace

Concept Flow - Subsets Generation Using Bitmask

Start with input array

↓

Calculate total subsets = 2^n

↓

For each number from 0 to 2^n - 1

↓

Use bits of number as mask

↓

For each bit position

↓

Include element at bit position

↓

Add formed subset to result

↓

Repeat until all numbers processed

↓

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 Java

int[] arr = {1, 2, 3};
int n = arr.length;
int total = 1 << n;
for (int mask = 0; mask < total; mask++) {
  List<Integer> subset = new ArrayList<>();
  for (int i = 0; i < n; i++) {
    if ((mask & (1 << i)) != 0) subset.add(arr[i]);
  }
  System.out.println(subset);
}

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

Execution Table

Step	Mask (binary)	Operation	Included Elements	Subset Formed
1	000	Check bits: none set	None	[]
2	001	Bit 0 set → include arr[0]	[1]	[1]
3	010	Bit 1 set → include arr[1]	[2]	[2]
4	011	Bits 0,1 set → include arr[0], arr[1]	[1, 2]	[1, 2]
5	100	Bit 2 set → include arr[2]	[3]	[3]
6	101	Bits 0,2 set → include arr[0], arr[2]	[1, 3]	[1, 3]
7	110	Bits 1,2 set → include arr[1], arr[2]	[2, 3]	[2, 3]
8	111	Bits 0,1,2 set → include arr[0], arr[1], arr[2]	[1, 2, 3]	[1, 2, 3]
9	-	All masks processed	-	All subsets generated

💡 Mask reaches 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 (exit)
subset	[]	[]	[1]	[2]	[1, 2]	[3]	[1, 3]	[2, 3]	[1, 2, 3]	[]
Included Elements	None	None	[1]	[2]	[1, 2]	[3]	[1, 3]	[2, 3]	[1, 2, 3]	All subsets done

Key Moments - 3 Insights

Why do we use (mask & (1 << i)) != 0 to check if an element is included?

Because each bit in mask represents whether to include the element at position i. If the bit is 1, the element is included. This is shown in execution_table rows 2-8 where bits set correspond to included elements.

Why does the loop run from 0 to 2^n - 1?

Because 2^n represents all possible subsets of n elements. Each number from 0 to 2^n - 1 is a unique bit pattern representing one subset. The exit_note and execution_table row 9 confirm this.

What happens when mask is 0?

No bits are set, so no elements are included. The subset is empty []. This is shown in execution_table row 1.

Visual Quiz - 3 Questions

Look at the execution_table at Step 6. Which elements are included in the subset?

A [1, 3]

B [2, 3]

C [1, 2]

D [3]

💡 Hint

Check the 'Included Elements' column at Step 6 in execution_table.

At which step does the subset include all elements of the array?

A Step 7

B Step 8

C Step 5

D Step 4

💡 Hint

Look for the subset with all elements [1, 2, 3] in execution_table.

If the input array had 4 elements, how many total subsets would be generated?

A 8

B 4

C 16

D 32

💡 Hint

Recall total subsets = 2^n, check concept_flow for formula.

Concept Snapshot

Subsets Generation Using Bitmask:
- Total subsets = 2^n for array of size n
- Iterate mask from 0 to 2^n - 1
- For each bit i in mask, if set, include arr[i]
- Each mask represents one subset
- Efficient way to generate all subsets

Full Transcript

This concept shows how to generate all subsets of an array using bitmasking. We calculate total subsets as 2 to the power of the array length. Then, for each number from 0 up to one less than total subsets, we use its binary bits to decide which elements to include in the current subset. Each bit corresponds to an element's position. If the bit is 1, we include that element. This way, all possible combinations are covered. The execution table traces each mask value, the bits set, and the subset formed. The variable tracker shows how mask and subsets change step by step. Key moments clarify why bitwise checks are used and why the loop runs up to 2^n. The visual quiz tests understanding of included elements and total subsets. This method is a simple and fast way to list all subsets.

Practice

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

easy

A. All possible subsets of the set

B. Only the largest subset of the set

C. Only subsets with even number of elements

D. Only subsets with odd 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 bitmask

   By iterating through all bitmasks from 0 to 2^n - 1, we get all possible subsets of the set.

3. Final Answer:

   All possible subsets of the set -> Option A

4. Quick Check:

   Bitmask = subsets generator [OK]

Hint: Bitmask bits map directly to subset elements included [OK]

Common Mistakes:

• Thinking bitmask generates only largest subsets
• Confusing bitmask with subsets of fixed size
• Ignoring subsets with zero elements

2. Which of the following Java code snippets correctly initializes the loop to generate all subsets of an array arr of length n using bitmask?

easy

A. for (int mask = 0; mask < n; mask++)

B. for (int mask = 1; mask <= n; mask++)

C. for (int mask = 0; mask <= n; mask++)

D. for (int mask = 0; mask < (1 << n); mask++)

Solution

1. Step 1: Understand bitmask range

   Bitmask runs from 0 to 2^n - 1, which is (1 << n) in Java.

2. Step 2: Check loop syntax

   The loop must start at 0 and run while mask is less than (1 << n), so for (int mask = 0; mask < (1 << n); mask++) is correct.

3. Final Answer:

   for (int mask = 0; mask < (1 << n); mask++) -> Option D

4. Quick Check:

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

Hint: Use (1 << n) for 2^n subsets count [OK]

Common Mistakes:

• Starting loop from 1 instead of 0
• Using <= n instead of < 2^n
• Confusing n with 2^n in loop condition

3. What is the output of the following Java code snippet?

int[] arr = {1, 2};
for (int mask = 0; mask < (1 << arr.length); mask++) {
    System.out.print("{");
    for (int i = 0; i < arr.length; i++) {
        if ((mask & (1 << i)) != 0) {
            System.out.print(arr[i] + " ");
        }
    }
    System.out.print("} ");
}

medium

A. {} {1 } {2 } {1 2 }

B. {1 } {2 } {1 2 } {}

C. {} {2 } {1 } {1 2 }

D. {1 2 } {1 } {2 } {}

Solution

1. Step 1: Understand bitmask values

   arr.length = 2, so mask goes from 0 to 3 (0b00 to 0b11).

2. Step 2: Trace each mask iteration

   mask=0 (0b00): no bits set, prints {}
   mask=1 (0b01): bit 0 set, prints {1 }
   mask=2 (0b10): bit 1 set, prints {2 }
   mask=3 (0b11): bits 0 and 1 set, prints {1 2 }

3. Final Answer:

   { } {1 } {2 } {1 2 } -> Option A

4. Quick Check:

   Bitmask subsets printed in order [OK]

Hint: Mask bits show which elements print [OK]

Common Mistakes:

• Mixing order of subsets
• Printing subsets without braces
• Confusing bit positions with array indices

4. Identify the error in the following Java code that attempts to generate all subsets using bitmask:

int[] arr = {1, 2, 3};
for (int mask = 0; mask <= (1 << arr.length); mask++) {
    for (int i = 0; i < arr.length; i++) {
        if ((mask & (1 << i)) > 0) {
            System.out.print(arr[i] + " ");
        }
    }
    System.out.println();
}

medium

A. Inner loop should run from i = 1 to arr.length.

B. Bitwise AND condition should use == 0 instead of > 0.

C. Loop condition should be mask < (1 << arr.length), not <=.

D. Array length should be decremented by 1 in loop conditions.

Solution

1. Step 1: Check loop range correctness

   mask runs from 0 to 2^n - 1, so mask < (1 << arr.length) is correct. Using <= causes one extra iteration beyond valid range.

2. Step 2: Verify bitwise condition and loops

   (mask & (1 << i)) > 0 is valid to check if bit is set. Inner loop from 0 to arr.length is correct.

3. Final Answer:

   Loop condition should be mask < (1 << arr.length), not <=. -> Option C

4. Quick Check:

   Loop must not exceed 2^n - 1 [OK]

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

Common Mistakes:

• Using <= causes out-of-range mask
• Incorrect bitwise condition operators
• Starting inner loop at 1 instead of 0

5. Given an integer array arr = {1, 2, 3, 4}, how many subsets generated by bitmask will have an even sum of elements?

hard

A. 6

B. 8

C. 7

D. 9

Solution

1. Step 1: Calculate total subsets

   For 4 elements, total subsets = 2^4 = 16.

2. Step 2: Count subsets with even sum

   Half of the subsets of a set with consecutive integers have even sum. So, 16 / 2 = 8 subsets.

3. Final Answer:

   8 -> Option B

4. Quick Check:

   Half subsets have even sum for consecutive integers [OK]

Hint: Half subsets have even sum for consecutive integers [OK]

Common Mistakes:

• Counting total subsets as answer
• Assuming all subsets have even sum
• Miscounting subsets with odd sums