Subsets Generation Using Bitmask in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start the loop for generating subsets using bitmask.

DSA Java

for (int mask = [1]; mask < (1 << nums.length); mask++) {
    // generate subset
}

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

A0

Bnums.length

C-1

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting mask from 1 misses the empty subset.

Using nums.length as start causes incorrect loop.

The bitmask starts from 0 to represent the empty subset and goes up to 2^n - 1.

2fill in blank

medium

Complete the code to check if the j-th element is included in the current subset mask.

DSA Java

if ((mask & (1 << [1])) != 0) {
    subset.add(nums[j]);
}

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

Aj

Bmask

Cnums.length

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using mask or i instead of j in the bit shift.

Not using bitwise AND to check the bit.

We check the j-th bit of mask to see if the element at index j is included.

3fill in blank

hard

Fix the error in the inner loop to iterate over all elements for subset generation.

DSA Java

for (int [1] = 0; j < nums.length; j++) {
    if ((mask & (1 << j)) != 0) {
        subset.add(nums[j]);
    }
}

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

Ai

Bk

Cm

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using i in the loop header but j inside causes errors.

Using a variable not declared or mismatched.

The loop variable must be j to match the condition and indexing inside the loop.

4fill in blank

hard

Fill both blanks to correctly initialize and add the subset to the result list.

DSA Java

List<Integer> subset = new ArrayList<>();
// add elements to subset
result.[1](subset);

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

Aclear

Bremove

Cadd

Dcontains

Attempts:

3 left

💡 Hint

Common Mistakes

Using remove or clear instead of add.

Trying to use contains which only checks presence.

We add the generated subset to the result list using add method.

5fill in blank

hard

Fill all three blanks to complete the subsets generation method using bitmask.

DSA Java

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;
    for (int mask = [1]; mask < (1 << n); mask++) {
        List<Integer> subset = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            if ((mask & (1 << [2])) != 0) {
                subset.add(nums[[3]]);
            }
        }
        result.add(subset);
    }
    return result;
}

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

A0

Bj

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Starting mask from 1 misses empty subset.

Using i instead of j in bit check or indexing.

The outer loop starts from 0. The bit check uses j, and the element added is nums[j].

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