Subsets Generation Using Bitmask in DSA Javascript - 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

↓

If bit is 1, include element

↓

Add formed subset to result

↓

Repeat until all numbers processed

↓

Return all subsets

We use numbers from 0 to 2^n - 1 as masks. Each bit shows if an element is in the subset.

Execution Sample

DSA Javascript

const subsets = (nums) => {
  const result = [];
  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)) subset.push(nums[i]);
    }
    result.push(subset);
  }
  return result;
};

Generates all subsets of nums by using bitmask from 0 to 2^n - 1.

Execution Table

Step	Mask (binary)	Subset formed	Bit checked	Action	Resulting Subset
1	000	Start mask=0	Bit 0	0 & 1=0 (exclude)	[]
2	000	mask=0	Bit 1	0 & 2=0 (exclude)	[]
3	000	mask=0	Bit 2	0 & 4=0 (exclude)	[]
4	000	mask=0 done	-	Add subset	[]
5	001	Start mask=1	Bit 0	1 & 1=1 (include)	[1]
6	001	mask=1	Bit 1	1 & 2=0 (exclude)	[1]
7	001	mask=1	Bit 2	1 & 4=0 (exclude)	[1]
8	001	mask=1 done	-	Add subset	[1]
9	010	Start mask=2	Bit 0	2 & 1=0 (exclude)	[]
10	010	mask=2	Bit 1	2 & 2=2 (include)	[2]
11	010	mask=2	Bit 2	2 & 4=0 (exclude)	[2]
12	010	mask=2 done	-	Add subset	[2]
13	011	Start mask=3	Bit 0	3 & 1=1 (include)	[1]
14	011	mask=3	Bit 1	3 & 2=2 (include)	[1,2]
15	011	mask=3	Bit 2	3 & 4=0 (exclude)	[1,2]
16	011	mask=3 done	-	Add subset	[1,2]
17	100	Start mask=4	Bit 0	4 & 1=0 (exclude)	[]
18	100	mask=4	Bit 1	4 & 2=0 (exclude)	[]
19	100	mask=4	Bit 2	4 & 4=4 (include)	[3]
20	100	mask=4 done	-	Add subset	[3]
21	101	Start mask=5	Bit 0	5 & 1=1 (include)	[1]
22	101	mask=5	Bit 1	5 & 2=0 (exclude)	[1]
23	101	mask=5	Bit 2	5 & 4=4 (include)	[1,3]
24	101	mask=5 done	-	Add subset	[1,3]
25	110	Start mask=6	Bit 0	6 & 1=0 (exclude)	[]
26	110	mask=6	Bit 1	6 & 2=2 (include)	[2]
27	110	mask=6	Bit 2	6 & 4=4 (include)	[2,3]
28	110	mask=6 done	-	Add subset	[2,3]
29	111	Start mask=7	Bit 0	7 & 1=1 (include)	[1]
30	111	mask=7	Bit 1	7 & 2=2 (include)	[1,2]
31	111	mask=7	Bit 2	7 & 4=4 (include)	[1,2,3]
32	111	mask=7 done	-	Add subset	[1,2,3]
33	-	All masks done	-	-	All subsets generated

💡 mask reaches 2^3=8, loop ends after mask=7

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	0	0	1	2	3	4	5	6	7	8 (exit)
subset	[]	[]	[1]	[2]	[1,2]	[3]	[1,3]	[2,3]	[1,2,3]	N/A
result.length	0	1	2	3	4	5	6	7	8	8

Key Moments - 3 Insights

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

Because (1 << n) equals 2^n, which is the total number of subsets for n elements. See execution_table rows 1 and 33 where mask goes from 0 to 7 (2^3 -1).

How does the bitmask decide which elements to include?

Each bit in mask corresponds to an element index. If bit i is 1, element i is included. Check execution_table rows 5-7 for mask=1 (binary 001) including only element 0.

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

Because (1 << i) creates a number with only bit i set. ANDing with mask tells if bit i is set in mask. See execution_table rows 5, 6, 7 for bit checks.

Visual Quiz - 3 Questions

Look at the execution_table at step 14, which elements are included in the subset?

A [1, 2]

B [2, 3]

C [1, 3]

D [3]

💡 Hint

Check the 'Resulting Subset' column at step 14 in execution_table.

At which mask value does the subset [2,3] get formed?

A mask=6

B mask=5

C mask=3

D mask=7

💡 Hint

Look for subset [2,3] in the 'Resulting Subset' column in execution_table.

If the input array had 4 elements, how many total subsets would the loop generate?

A 8

B 16

C 4

D 32

💡 Hint

Recall from key_moments that total subsets = 2^n, check variable_tracker for mask max.

Concept Snapshot

Subsets Generation Using Bitmask:
- Use numbers 0 to 2^n - 1 as masks
- Each bit in mask shows if element is included
- For each mask, build subset by checking bits
- Total subsets = 2^n
- Efficient way to generate all subsets

Full Transcript

This concept shows how to generate all subsets of an array using bitmasks. We use numbers from 0 to 2^n - 1, where n is the array length. Each number's bits represent whether to include each element. For example, if bit 0 is 1, include element 0. We loop through all masks, build subsets by checking bits, and collect them. The total subsets are 2^n. The execution table traces each mask, bit checked, and subset formed. Variable tracker shows mask and subsets after each step. Key moments clarify why we use 2^n and how bits decide inclusion. The visual quiz tests understanding of subsets formed at specific steps and total subsets count. This method is a simple, clear way to generate all subsets.

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