Subsets Generation Using Bitmask in DSA Java

Mental Model

Each subset can be represented by a series of on/off switches, where each switch decides if an element is included or not.

Analogy: Imagine you have a row of light switches, each controlling a lamp. Turning a switch on means including that lamp in the room's lighting (subset), turning it off means excluding it.

Elements: [a] [b] [c]
Bitmask:  0    1    0
Subset:   exclude a, include b, exclude c

Dry Run Walkthrough

Input: list: [a, b, c]

Goal: Generate all subsets of [a, b, c] using bitmask representation

Step 1: Start with bitmask 000 (binary for 0), meaning no elements included

bitmask=000 -> subset=[]

Why: This represents the empty subset

Step 2: Move to bitmask 001 (binary for 1), include only element at index 0

bitmask=001 -> subset=[a]

Why: Only the first element is included

Step 3: Move to bitmask 010 (binary for 2), include only element at index 1

bitmask=010 -> subset=[b]

Why: Only the second element is included

Step 4: Move to bitmask 011 (binary for 3), include elements at index 0 and 1

bitmask=011 -> subset=[a, b]

Why: First and second elements included

Step 5: Move to bitmask 100 (binary for 4), include only element at index 2

bitmask=100 -> subset=[c]

Why: Only the third element is included

Step 6: Move to bitmask 101 (binary for 5), include elements at index 0 and 2

bitmask=101 -> subset=[a, c]

Why: First and third elements included

Step 7: Move to bitmask 110 (binary for 6), include elements at index 1 and 2

bitmask=110 -> subset=[b, c]

Why: Second and third elements included

Step 8: Move to bitmask 111 (binary for 7), include all elements

bitmask=111 -> subset=[a, b, c]

Why: All elements included

Result:

All subsets generated: [] [a] [b] [a, b] [c] [a, c] [b, c] [a, b, c]

Annotated Code

DSA Java

import java.util.*;

public class SubsetsBitmask {

    public static List<List<String>> generateSubsets(List<String> elements) {
        List<List<String>> allSubsets = new ArrayList<>();
        int n = elements.size();
        int total = 1 << n; // total subsets = 2^n

        for (int bitmask = 0; bitmask < total; bitmask++) {
            List<String> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((bitmask & (1 << i)) != 0) {
                    subset.add(elements.get(i));
                }
            }
            allSubsets.add(subset);
        }
        return allSubsets;
    }

    public static void main(String[] args) {
        List<String> input = Arrays.asList("a", "b", "c");
        List<List<String>> subsets = generateSubsets(input);
        for (List<String> subset : subsets) {
            System.out.println(subset);
        }
    }
}

int total = 1 << n; // total subsets = 2^n

Calculate total number of subsets by shifting 1 left n times

for (int bitmask = 0; bitmask < total; bitmask++) {

Iterate through all bitmask values representing subsets

if ((bitmask & (1 << i)) != 0) {

Check if the i-th bit in bitmask is set to include element i

subset.add(elements.get(i));

Add element i to current subset if bit is set

allSubsets.add(subset);

Add the constructed subset to the list of all subsets

Output

[]

[a]

[b]

[a, b]

[c]

[a, c]

[b, c]

[a, b, c]

Complexity Analysis

Time: O(n * 2^n) because we generate 2^n subsets and each subset can take up to n steps to build

Space: O(n * 2^n) because we store all subsets and each subset can have up to n elements

vs Alternative: Compared to recursive backtracking, bitmask is often simpler and uses iterative loops, but both have similar time and space complexity

Edge Cases

empty list

Returns a list with one subset: the empty subset []

DSA Java

int total = 1 << n; // total subsets = 2^n

single element list

Returns two subsets: [] and [element]

DSA Java

for (int bitmask = 0; bitmask < total; bitmask++) {

When to Use This Pattern

When you need to generate all subsets or combinations of a set, especially when the set size is small, bitmasking is a quick and clear approach to represent inclusion/exclusion.

Common Mistakes

Mistake: Using 1 << i without parentheses in bitmask & 1 << i, causing wrong precedence
Fix: Use parentheses: (bitmask & (1 << i)) to ensure correct bit checking

Mistake: Not iterating bitmask up to 2^n, missing some subsets
Fix: Calculate total subsets as 1 << n and loop bitmask from 0 to total-1

Summary

Generates all subsets of a list by treating each subset as a bitmask where bits represent element inclusion.

Use it when you want to list every possible combination of elements from a small set.

The key insight is that each subset corresponds to a unique binary number from 0 to 2^n - 1.

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