Subsets Generation Using Bitmask in DSA Typescript

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: [a, b, c]
Bitmask positions: 2 1 0
Example bitmask: 101
Subset: [a, c]

Representation:
Index:  2   1   0
Bits:  [1] [0] [1]
Set:    a   b   c

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 selected

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

bitmask=001 -> subset=[1]

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

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

bitmask=010 -> subset=[2]

Why: Second bit from right is 1, include second element

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

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

Why: Bits 0 and 1 are 1, include first two elements

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

bitmask=100 -> subset=[3]

Why: Third bit from right is 1, include third element

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

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

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

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

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

Why: Bits 1 and 2 are 1, 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, include all elements

Result:

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

Annotated Code

DSA Typescript

class SubsetsGenerator {
  static generateSubsets(nums: number[]): number[][] {
    const n = nums.length;
    const total = 1 << n; // total subsets = 2^n
    const result: number[][] = [];

    for (let bitmask = 0; bitmask < total; bitmask++) {
      const subset: number[] = [];
      for (let i = 0; i < n; i++) {
        if ((bitmask & (1 << i)) !== 0) {
          subset.push(nums[i]);
        }
      }
      result.push(subset);
    }

    return result;
  }
}

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

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

Calculate total number of subsets by shifting 1 left n times

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

Iterate through all bitmasks from 0 to 2^n - 1

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

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

subset.push(nums[i]);

Add element nums[i] to current subset if bit is set

result.push(subset);

Add the constructed 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 and each subset can have up to n elements

vs Alternative: Compared to recursive backtracking, bitmask is often simpler and faster for small n but both have similar exponential time

Edge Cases

empty input array

Returns one subset: the empty subset []

DSA Typescript

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

single element array

Returns two subsets: [] and [element]

DSA Typescript

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

When to Use This Pattern

When you need to generate all subsets of a small set, use bitmasking because it directly maps subsets to binary numbers for easy enumeration.

Common Mistakes

Mistake: Using 1 << i without parentheses causing wrong bit shift
Fix: Always use parentheses like (1 << i) to ensure correct bit shifting

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

Summary

Generates all subsets of a set by treating each subset as a binary number where bits represent element inclusion.

Use when you want to list every possible combination of elements in a small set efficiently.

The key insight is that each subset corresponds to a unique bit pattern 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