Subsets Generation Using Bitmask in DSA Java - Build from Scratch

Subsets Generation Using Bitmask

📖 Scenario: Imagine you have a small collection of unique fruits and you want to see all possible combinations of these fruits you can pick. This is like making different fruit baskets with any number of fruits from your collection.

🎯 Goal: You will write a Java program that uses bitmasking to generate and print all subsets of a given list of fruits.

📋 What You'll Learn

Create an array of fruits with exact values: "Apple", "Banana", "Cherry"

Create an integer variable called n to store the number of fruits

Use a for loop with variable mask from 0 to (1 << n) - 1 to generate subsets

Inside the loop, use another for loop with variable i from 0 to n - 1 to check bits

Print each subset as a list of fruits separated by spaces

💡 Why This Matters

🌍 Real World

Generating subsets is useful in situations like choosing combinations of items, testing different feature sets, or exploring options in decision-making.

💼 Career

Understanding bitmasking and subsets helps in coding interviews and solving problems related to combinations, optimization, and search algorithms.

1

Create the fruits array

Create a String array called fruits with these exact values: "Apple", "Banana", "Cherry"

DSA Java

// Create the fruits array with exact values
// Your code here

Hint

Use curly braces to list the fruits inside the array.

2

Create the variable for number of fruits

Create an integer variable called n and set it to the length of the fruits array

DSA Java

String[] fruits = {"Apple", "Banana", "Cherry"};
// Create an integer variable n for the number of fruits
// Your code here

Hint

Use fruits.length to get the number of fruits.

3

Generate subsets using bitmask

Use a for loop with variable mask from 0 to (1 << n) - 1. Inside it, use another for loop with variable i from 0 to n - 1. Check if the i-th bit of mask is set using ((mask & (1 << i)) != 0). If yes, print fruits[i] followed by a space.

DSA Java

String[] fruits = {"Apple", "Banana", "Cherry"};
int n = fruits.length;
// Use nested for loops to generate subsets using bitmask
// Your code here

Hint

Use bit shifting and bitwise AND to check if a fruit is in the current subset.

4

Print all subsets

Print all subsets generated by the bitmask loops. Each subset should be printed on its own line with fruits separated by spaces.

DSA Java

String[] fruits = {"Apple", "Banana", "Cherry"};
int n = fruits.length;
for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) {
            System.out.print(fruits[i] + " ");
        }
    }
    System.out.println();
}
// Output is printed by the loops above

Hint

Run the program to see all subsets printed line by line.

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