Subsets Generation Using Bitmask in DSA Typescript - Execution Trace

Concept Flow - Subsets Generation Using Bitmask

Start with input array

↓

Calculate total subsets = 2^n

↓

For each number from 0 to 2^n - 1

↓

Use bits of number as mask

↓

For each bit position

↓

Include element at that position

↓

Add formed subset to result

↓

Repeat until all numbers processed

↓

Return all subsets

We generate all subsets by counting from 0 to 2^n-1 and using each number's bits to decide which elements to include.

Execution Sample

DSA Typescript

const subsets = (nums: number[]): number[][] => {
  const result: number[][] = [];
  const n = nums.length;
  for (let mask = 0; mask < (1 << n); mask++) {
    const subset = [];
    for (let i = 0; i < n; i++) {
      if ((mask & (1 << i)) !== 0) subset.push(nums[i]);
    }
    result.push(subset);
  }
  return result;
};

This code generates all subsets of nums by using bitmask from 0 to 2^n-1 to decide which elements to include.

Execution Table

Step	Operation	Mask (binary)	Elements Included	Subset Formed	Result So Far
1	mask=0	000	none	[]	[[]]
2	mask=1	001	nums[0]=1	[1]	[[], [1]]
3	mask=2	010	nums[1]=2	[2]	[[], [1], [2]]
4	mask=3	011	nums[0]=1, nums[1]=2	[1, 2]	[[], [1], [2], [1, 2]]
5	mask=4	100	nums[2]=3	[3]	[[], [1], [2], [1, 2], [3]]
6	mask=5	101	nums[0]=1, nums[2]=3	[1, 3]	[[], [1], [2], [1, 2], [3], [1, 3]]
7	mask=6	110	nums[1]=2, nums[2]=3	[2, 3]	[[], [1], [2], [1, 2], [3], [1, 3], [2, 3]]
8	mask=7	111	nums[0]=1, nums[1]=2, nums[2]=3	[1, 2, 3]	[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

💡 mask reaches 2^n (8), all subsets generated

Variable Tracker

Variable	Start	After mask=0	After mask=1	After mask=2	After mask=3	After mask=4	After mask=5	After mask=6	After mask=7	Final
mask	undefined	0	1	2	3	4	5	6	7	8
subset	[]	[]	[1]	[2]	[1, 2]	[3]	[1, 3]	[2, 3]	[1, 2, 3]	N/A
result	[]	[[]]	[[], [1]]	[[], [1], [2]]	[[], [1], [2], [1, 2]]	[[], [1], [2], [1, 2], [3]]	[[], [1], [2], [1, 2], [3], [1, 3]]	[[], [1], [2], [1, 2], [3], [1, 3], [2, 3]]	[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]	Final result with all subsets

Key Moments - 3 Insights

Why do we use (1 << n) to set the loop limit?

Because 1 << n equals 2^n, which is the total number of subsets for n elements. This ensures we cover all possible subsets as each bitmask from 0 to 2^n-1 represents one subset (see execution_table rows 1 to 8).

How does the bitmask decide which elements to include?

Each bit in the mask corresponds to an index in the array. If the bit is 1, we include that element. For example, mask=5 (binary 101) includes elements at positions 0 and 2 (see execution_table row 6).

Why do we check bits using (mask & (1 << i))?

Because (1 << i) creates a number with only the ith bit set. Using & with mask checks if that bit is set in mask. If yes, we include nums[i]. This is shown in the inner loop of the code and reflected in the subsets formed in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what subset is formed at step 4 when mask=3?

A [1, 3]

B [1, 2]

C [2, 3]

D []

💡 Hint

Check the 'Subset Formed' column at step 4 in execution_table.

At which mask value does the subset include all elements?

A mask=6

B mask=4

C mask=7

D mask=0

💡 Hint

Look for the subset with all elements in the 'Subset Formed' column in execution_table.

If the input array length was 4, how many total subsets would the loop generate?

A 16

B 12

C 8

D 4

💡 Hint

Recall the loop runs from 0 to 2^n - 1, where n is array length, as explained in key_moments.

Concept Snapshot

Subsets Generation Using Bitmask:
- Total subsets = 2^n for array length n
- Loop mask from 0 to 2^n - 1
- Each bit in mask decides inclusion of element
- Use (mask & (1 << i)) to check bits
- Collect elements where bit is 1
- Result contains all subsets

Full Transcript

This concept shows how to generate all subsets of an array using bitmasking. We count from 0 to 2^n - 1, where n is the number of elements. Each number's binary form acts as a mask: each bit corresponds to an element's inclusion or exclusion. For each mask, we check each bit; if the bit is 1, we include that element in the current subset. We collect all subsets this way. The execution table traces each mask, the bits set, the subset formed, and the growing result. Key moments clarify why 2^n subsets exist, how bits map to elements, and how bitwise AND checks bits. The visual quiz tests understanding of subsets formed at specific steps and the total count for different array sizes.

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