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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of subsets generated by bitmask

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

DSA Java

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

A

{},
{2,},
{1,2,},
{1,},

B

{},
{1,},
{2,},
{1,2,},

C

{},
{1,},
{1,2,},
{2,},

D

{},
{2,},
{1,},
{1,2,},

💡 Hint

Think about how the bitmask counts from 0 to 2^n - 1 and which bits correspond to which elements.

The bitmask runs from 0 to 3 (for 2 elements). For each mask, bits set to 1 include the corresponding element. Mask 0 includes none, mask 1 includes first element, mask 2 includes second element, mask 3 includes both.

🧠 Conceptual

intermediate

Number of subsets generated by bitmask

If you have an array of length 4, how many subsets will the bitmask method generate?

A 16

B 8

C 4

D 12

💡 Hint

Each element can be either included or excluded independently.

For n elements, there are 2^n subsets. For 4 elements, 2^4 = 16 subsets.

🔧 Debug

advanced

Identify the error in subset generation code

What error does the following Java code produce when generating subsets using bitmask for array [1, 2, 3]? int[] nums = {1, 2, 3}; for (int mask = 0; mask <= (1 << nums.length); mask++) { System.out.print("{"); for (int i = 0; i < nums.length; i++) { if ((mask & (1 << i)) != 0) { System.out.print(nums[i] + ","); } } System.out.println("}"); }

A Compilation error

B No error, runs correctly

C Infinite loop

D ArrayIndexOutOfBoundsException

💡 Hint

Check the loop condition for mask and the maximum value it takes.

The loop runs mask from 0 to (1 << nums.length) inclusive, which is 8 for length 3. But masks go from 0 to 7. When mask=8, bit operations access beyond array length causing ArrayIndexOutOfBoundsException.

❓ Predict Output

advanced

Output of subsets with empty subset excluded

What is the output of this Java code that generates all non-empty subsets of [1, 2, 3] using bitmask?

DSA Java

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

A

{1,}
{2,}
{3,}
{1,2,}
{1,3,}
{2,3,}
{1,2,3,}
{}

B

{}
{1,}
{2,}
{3,}
{1,2,}
{1,3,}
{2,3,}
{1,2,3,}

C

{1,}
{2,}
{1,2,}
{3,}
{1,3,}
{2,3,}
{1,2,3,}

D

{1,2,3,}
{1,2,}
{1,3,}
{2,3,}
{1,}
{2,}
{3,}

💡 Hint

Mask starts at 1, so empty subset is excluded.

Masks from 1 to 7 generate all subsets except empty. The order is ascending mask value, so subsets appear in increasing size and bit pattern order.

🧠 Conceptual

expert

Bitmask subset generation complexity

What is the time complexity of generating all subsets of an array of length n using the bitmask method?

A O(n * 2^n)

B O(n^2)

C O(2^n)

D O(n)

💡 Hint

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

There are 2^n subsets. For each subset, we check up to n elements to decide inclusion. So total time is O(n * 2^n).

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