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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of subsets generated by bitmask

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

DSA Javascript

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

A [[], [1], [2], [1, 2]]

B [[], [2], [1], [2, 1]]

C [[1], [], [2], [1, 2]]

D [[1, 2], [1], [2], []]

💡 Hint

Think about how bitmask represents subsets by including elements where bits are set.

The code uses bitmask from 0 to 3 (2^2 - 1). For each mask, it includes elements where the bit is 1. Mask 0 means no elements, mask 1 means first element, mask 2 means second element, mask 3 means both elements.

❓ Predict Output

intermediate

Number of subsets generated by bitmask

How many subsets will be generated by the following code for the array [5, 10, 15]?

DSA Javascript

const nums = [5, 10, 15];
const subsets = [];
for (let mask = 0; mask < (1 << nums.length); mask++) {
  const subset = [];
  for (let i = 0; i < nums.length; i++) {
    if (mask & (1 << i)) {
      subset.push(nums[i]);
    }
  }
  subsets.push(subset);
}
console.log(subsets.length);

A 3

B 8

C 6

D 7

💡 Hint

Number of subsets of an array of length n is 2^n.

For an array of length 3, total subsets are 2^3 = 8, including the empty subset.

🔧 Debug

advanced

Identify the error in bitmask subset generation

What error will the following code produce when generating subsets using bitmask for [1, 2, 3]?

DSA Javascript

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

A 9

B 8

C SyntaxError

D TypeError

💡 Hint

Check the loop condition for mask and how many iterations it runs.

The loop runs from mask = 0 to mask = 8 inclusive, so total 9 iterations, but subsets for length 3 should be 8.

❓ Predict Output

advanced

Output of subsets with filtering condition

What is the output of the following code that generates subsets of [1, 2, 3] but only includes subsets with sum greater than 3?

DSA Javascript

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

A [[2, 3], [1, 2, 3]]

B [[3], [1, 3], [2, 3], [1, 2, 3]]

C [[1, 3], [2, 3], [1, 2, 3]]

D [[1, 2, 3]]

💡 Hint

Calculate sums of subsets and check which are greater than 3.

Subsets with sum > 3 are [1,3] (sum 4), [2,3] (sum 5), and [1,2,3] (sum 6). Single element [3] sum is 3, not greater.

🧠 Conceptual

expert

Maximum subsets generated by bitmask for n elements

For an array of length n, what is the maximum number of subsets generated using bitmask technique?

A n^2

B n

C n!

D 2^n

💡 Hint

Think about how each element can be either included or excluded independently.

Each element has 2 choices: include or exclude. So total subsets are 2 multiplied by itself n times = 2^n.

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