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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of subsets generated by bitmask

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

DSA Typescript

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

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

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

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

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

💡 Hint

Think about how bitmask from 0 to 2^n - 1 represents subsets.

The bitmask runs from 0 to 3 (2^2 - 1). For each bitmask, bits set to 1 indicate inclusion of the element at that index. So 0 (00) means empty subset, 1 (01) means [1], 2 (10) means [2], and 3 (11) means [1, 2].

❓ Predict Output

intermediate

Number of subsets generated by bitmask

How many subsets will be generated by the bitmask approach for an input array of length 4?

DSA Typescript

const nums = [10, 20, 30, 40];
const subsets: number[][] = [];
for (let mask = 0; mask < (1 << nums.length); mask++) {
  const subset: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    if ((mask & (1 << i)) !== 0) {
      subset.push(nums[i]);
    }
  }
  subsets.push(subset);
}
console.log(subsets.length);

A 8

B 4

C 16

D 32

💡 Hint

Number of subsets of a set with n elements is 2^n.

For an array of length 4, the number of subsets is 2^4 = 16.

🔧 Debug

advanced

Identify the error in subset generation code

What error will the following TypeScript code produce when generating subsets using bitmask?

DSA Typescript

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

A The code runs fine and outputs 8

B Runtime error: index out of bounds

C SyntaxError due to invalid bitwise operation

D Outputs 9 subsets, one extra invalid subset

💡 Hint

Check the loop condition for mask variable.

The loop runs from 0 to 8 inclusive, but 1 << 3 = 8, so mask goes up to 8 which is out of range for subsets of length 3. This causes one extra subset to be generated.

❓ Predict Output

advanced

Output of subsets with filtering condition

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

DSA Typescript

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

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

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

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

D [[1, 2, 3]]

💡 Hint

Calculate sums of all subsets and check which are > 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 > 3, so excluded.

🧠 Conceptual

expert

Maximum subsets generated by bitmask for n elements

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

A 2^n

B n^2

C n!

D n * 2

💡 Hint

Recall the total number of subsets of a set.

The total number of subsets of a set with n elements is 2^n, which is the number of bitmasks from 0 to 2^n - 1.

Practice

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

easy

A. Only the largest subset

B. Only subsets with odd number of elements

C. Only subsets with even number of elements

D. All possible subsets of the set

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 cover all combinations of elements, thus all subsets.

3. Final Answer:

   All possible subsets of the set -> Option D

4. Quick Check:

   Bitmask = All subsets [OK]

Hint: Bitmask from 0 to 2^n-1 covers all subsets [OK]

Common Mistakes:

• Thinking bitmask generates only even or odd subsets
• Confusing subsets with permutations
• Assuming bitmask generates only largest subsets

2. Which of the following TypeScript code snippets correctly initializes the bitmask loop for generating subsets of an array arr of length n?

easy

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

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

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

D. for (let mask = 0; 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 code.

2. Step 2: Check loop correctness

   Loop from 0 to less than (1 << n) correctly iterates all bitmasks representing subsets.

3. Final Answer:

   for (let mask = 0; mask < (1 << n); mask++) {} -> Option C

4. Quick Check:

   Loop 0 to 2^n-1 = for (let mask = 0; mask < (1 << n); mask++) {} [OK]

Hint: Use (1 << n) for total subsets count [OK]

Common Mistakes:

• Using mask <= n instead of mask < 2^n
• Starting loop from 1 misses empty subset
• Using mask < n only covers single elements

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

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

medium

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

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

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

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

Solution

1. Step 1: Understand bitmask iteration

   Loop runs from 0 to 7 (2^3 - 1), generating all subsets of 3 elements.

2. Step 2: Trace subsets generated

   Each mask selects elements where bit is set, producing all subsets including empty and full set.

3. Final Answer:

   [[], ["a"], ["b"], ["a", "b"], ["c"], ["a", "c"], ["b", "c"], ["a", "b", "c"]] -> Option B

4. Quick Check:

   All subsets of 3 elements = [[], ["a"], ["b"], ["a", "b"], ["c"], ["a", "c"], ["b", "c"], ["a", "b", "c"]] [OK]

Hint: Bitmask 0 to 7 covers all subsets of 3 elements [OK]

Common Mistakes:

• Missing empty subset []
• Incorrect order or missing subsets
• Confusing subsets with permutations

4. Identify the error in this TypeScript code for generating subsets using bitmask:

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

medium

A. The outer loop should run while mask < (1 << n), not <=

B. The inner loop should run from i = 1 to n

C. The bitwise AND condition should be == 0 instead of truthy check

D. The subset array should be declared outside the loops

Solution

1. Step 1: Check outer loop range

   Loop runs from 0 to (1 << n) inclusive, which is one too many iterations (should be less than).

2. Step 2: Understand consequences

   When mask equals (1 << n), it exceeds the maximum bitmask for subsets, causing an extra invalid iteration.

3. Final Answer:

   The outer loop should run while mask < (1 << n), not <= -> Option A

4. Quick Check:

   Loop limit off by one = The outer loop should run while mask < (1 << n), not <= [OK]

Hint: Use mask < 2^n, not <= 2^n [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Changing inner loop range incorrectly
• Misusing bitwise condition checks

5. Given an array arr = [1, 2, 2], which code modification correctly generates all unique subsets using bitmask technique?

hard

A. Use a Set to store stringified subsets to avoid duplicates

B. Sort the array and skip adding duplicates inside inner loop

C. Increase bitmask range to (1 << (n+1)) to cover duplicates

D. No modification needed; bitmask handles duplicates automatically

Solution

1. Step 1: Understand duplicates in subsets

   Bitmask generates subsets by position, so duplicates in array cause duplicate subsets.

2. Step 2: Avoid duplicates using a Set

   Storing subsets as strings in a Set removes duplicates by keeping only unique subsets.

3. Final Answer:

   Use a Set to store stringified subsets to avoid duplicates -> Option A

4. Quick Check:

   Set removes duplicate subsets [OK]

Hint: Use Set to filter duplicate subsets from duplicates in array [OK]

Common Mistakes:

• Assuming bitmask alone removes duplicates
• Increasing bitmask range unnecessarily
• Trying to skip duplicates without sorting or tracking