Subsets Generation Using Bitmask in DSA Javascript

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; off means excluding it. Every combination of on/off switches creates a unique lighting setup, just like every combination of elements forms a unique subset.

Set: [1, 2, 3]
Bitmask positions: 2 1 0
Example bitmask: 101
Subset: includes elements at positions with 1 -> 1 and 3

[1] [2] [3]
 ↑   ↑   ↑
 2^2 2^1 2^0

Bitmask 101 means: include 1st and 3rd elements, exclude 2nd.

Dry Run Walkthrough

Input: set: [1, 2, 3]

Goal: Generate all subsets of [1, 2, 3] using bitmask representation

Step 1: Start with bitmask 000 (decimal 0), no elements included

bitmask=000 -> subset: []

Why: This represents the empty subset with no elements included

Step 2: Bitmask 001 (decimal 1), include element at position 0

bitmask=001 -> subset: [1]

Why: The rightmost bit is 1, so include the first element

Step 3: Bitmask 010 (decimal 2), include element at position 1

bitmask=010 -> subset: [2]

Why: The middle bit is 1, so include the second element

Step 4: Bitmask 011 (decimal 3), include elements at positions 0 and 1

bitmask=011 -> subset: [1, 2]

Why: Bits 0 and 1 are 1, so include first and second elements

Step 5: Bitmask 100 (decimal 4), include element at position 2

bitmask=100 -> subset: [3]

Why: The leftmost bit is 1, so include the third element

Step 6: Bitmask 101 (decimal 5), include elements at positions 0 and 2

bitmask=101 -> subset: [1, 3]

Why: Bits 0 and 2 are 1, so include first and third elements

Step 7: Bitmask 110 (decimal 6), include elements at positions 1 and 2

bitmask=110 -> subset: [2, 3]

Why: Bits 1 and 2 are 1, so include second and third elements

Step 8: Bitmask 111 (decimal 7), include all elements

bitmask=111 -> subset: [1, 2, 3]

Why: All bits are 1, so include all elements

Result:

All subsets generated:
[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

Annotated Code

DSA Javascript

class SubsetsGenerator {
  constructor(nums) {
    this.nums = nums;
  }

  generateSubsets() {
    const n = this.nums.length;
    const totalSubsets = 1 << n; // 2^n subsets
    const result = [];

    for (let bitmask = 0; bitmask < totalSubsets; bitmask++) {
      const subset = [];
      for (let j = 0; j < n; j++) {
        if ((bitmask & (1 << j)) !== 0) {
          subset.push(this.nums[j]);
        }
      }
      result.push(subset);
    }

    return result;
  }
}

// Driver code
const generator = new SubsetsGenerator([1, 2, 3]);
const subsets = generator.generateSubsets();
for (const subset of subsets) {
  console.log(JSON.stringify(subset));
}

const totalSubsets = 1 << n; // 2^n subsets

Calculate total number of subsets as 2 to the power of n

for (let bitmask = 0; bitmask < totalSubsets; bitmask++) {

Iterate over all bitmasks representing subsets

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

Check if j-th bit in bitmask is set to include nums[j]

subset.push(this.nums[j]);

Add element to current subset if bit is set

result.push(subset);

Add the formed subset to the result list

Output

[]

[1]

[2]

[1,2]

[3]

[1,3]

[2,3]

[1,2,3]

Complexity Analysis

Time: O(n * 2^n) because we generate 2^n subsets and check n bits for each

Space: O(n * 2^n) because we store all subsets, each up to size n

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

Edge Cases

empty set []

Only one subset: the empty subset []

DSA Javascript

const totalSubsets = 1 << n; // 2^n subsets

set with one element [5]

Two subsets: [] and [5]

DSA Javascript

for (let bitmask = 0; bitmask < totalSubsets; bitmask++) {

When to Use This Pattern

When asked to generate all subsets or power sets, especially with small sets, bitmasking is a quick way to represent inclusion/exclusion of elements.

Common Mistakes

Mistake: Using 1 << n without parentheses causing wrong precedence
Fix: Use parentheses: 1 << n to correctly compute 2^n

Mistake: Checking bits incorrectly, e.g., using bitmask & j instead of bitmask & (1 << j)
Fix: Use bitmask & (1 << j) to check the j-th bit properly

Summary

Generates all subsets of a set by treating each subset as a bitmask of included elements.

Use when you need to list all combinations of elements from a small set.

Each bit in a number represents whether to include an element, making subset generation simple and systematic.

Practice

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

easy

A. Only subsets with even number of elements

B. Only the largest subset

C. All possible subsets of the set

D. Only subsets with odd number of elements

Solution

1. Step 1: Understand bitmask representation

   Each bit in a bitmask represents whether an element is included (1) or excluded (0) from a subset.

2. Step 2: Generate subsets using bitmask

   By iterating through all bitmasks from 0 to 2^n - 1, we get all possible combinations of elements, i.e., all subsets.

3. Final Answer:

   All possible subsets of the set -> Option C

4. Quick Check:

   Bitmask = subsets [OK]

Hint: Bitmask bits map directly to subset inclusion [OK]

Common Mistakes:

• Thinking bitmask generates only largest subsets
• Confusing subsets with permutations
• Assuming bitmask filters subsets by size

2. Which of the following is the correct way to start a loop for generating subsets using bitmask for an array of length n in JavaScript?

easy

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

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

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

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

Solution

1. Step 1: Understand bitmask range

   Bitmask must cover all numbers from 0 to 2^n - 1, which is (1 << n) in JavaScript.

2. Step 2: Correct loop syntax

   The loop should start at 0 and run while mask is less than (1 << n), incrementing mask by 1 each time.

3. Final Answer:

   for (let mask = 0; mask < (1 << n); mask++) -> Option B

4. Quick Check:

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

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

Common Mistakes:

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

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

const arr = ["a", "b"];
const subsets = [];
for (let mask = 0; mask < (1 << arr.length); mask++) {
  let subset = [];
  for (let i = 0; i < arr.length; i++) {
    if ((mask & (1 << i)) !== 0) {
      subset.push(arr[i]);
    }
  }
  subsets.push(subset);
}
console.log(subsets);

medium

A. [[], ["a"], ["b"], ["a", "b"]]

B. [["a"], ["b"], ["a", "b"]]

C. [[], ["b"], ["a"], ["a", "b"]]

D. [["a", "b"]]

Solution

1. Step 1: Understand bitmask iterations

   For arr length 2, mask runs from 0 to 3 (0b00 to 0b11), generating 4 subsets.

2. Step 2: Map mask bits to elements

   mask=0 (0b00) -> [], mask=1 (0b01) -> ["a"], mask=2 (0b10) -> ["b"], mask=3 (0b11) -> ["a", "b"]

3. Final Answer:

   [[], ["a"], ["b"], ["a", "b"]] -> Option A

4. Quick Check:

   All subsets of ["a", "b"] listed [OK]

Hint: Check bit positions for element inclusion [OK]

Common Mistakes:

• Missing empty subset []
• Swapping order of subsets
• Ignoring bitmask 0 producing empty subset

4. Identify the error in the following code snippet for generating subsets using bitmask:

const arr = [1, 2, 3];
const subsets = [];
for (let mask = 0; mask <= (1 << arr.length); mask++) {
  let subset = [];
  for (let i = 0; i < arr.length; i++) {
    if (mask & (1 << i)) {
      subset.push(arr[i]);
    }
  }
  subsets.push(subset);
}
console.log(subsets);

medium

A. The subsets array should be cleared inside the outer loop.

B. The inner loop should run until i <= arr.length.

C. The bitwise AND condition should be (mask | (1 << i)) instead of &.

D. The outer loop condition should be mask < (1 << arr.length), not <=.

Solution

1. Step 1: Check outer loop range

   The outer loop runs from 0 to (1 << arr.length) inclusive, which is one too many iterations (should be less than).

2. Step 2: Correct loop condition

   It should be mask < (1 << arr.length) to avoid an extra invalid subset iteration.

3. Final Answer:

   The outer loop condition should be mask < (1 << arr.length), not <=. -> Option D

4. Quick Check:

   Loop runs 2^n times, not 2^n+1 [OK]

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

Common Mistakes:

• Using <= instead of < in loop condition
• Confusing bitwise AND (&) with OR (|)
• Extending inner loop beyond array length

5. Given an array arr = [1, 2, 3, 4], how many subsets will be generated by the bitmask method, and what is the subset generated when mask = 9? (mask is in decimal)

hard

A. 16 subsets; subset for mask 9 is [1, 4]

B. 8 subsets; subset for mask 9 is [2, 3]

C. 16 subsets; subset for mask 9 is [2, 4]

D. 15 subsets; subset for mask 9 is [1, 3, 4]

Solution

1. Step 1: Calculate total subsets for array length 4

   Total subsets = 2^4 = 16.

2. Step 2: Decode mask 9 in binary and map to elements

   9 in binary is 1001. Bits set at positions 0 and 3 correspond to arr[0] = 1 and arr[3] = 4.

3. Final Answer:

   16 subsets; subset for mask 9 is [1, 4] -> Option A

4. Quick Check:

   2^4 = 16 subsets; mask 9 = 1001 binary [OK]

Hint: Convert mask to binary, map bits to elements [OK]

Common Mistakes:

• Miscounting total subsets as 15
• Misinterpreting binary mask bits
• Confusing element indices with bit positions