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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of subsets generated by bitmask

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

DSA Python

nums = [1, 2]
subsets = []
n = len(nums)
for mask in range(1 << n):
    subset = []
    for i in range(n):
        if mask & (1 << i):
            subset.append(nums[i])
    subsets.append(subset)
print(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 inclusion of elements in subsets.

The bitmask runs from 0 to 3 (00 to 11 in binary). For each bit set, the corresponding element is included. 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 a list of 4 elements?

DSA Python

nums = [10, 20, 30, 40]
n = len(nums)
count = 0
for mask in range(1 << n):
    count += 1
print(count)

A 16

B 8

C 4

D 32

💡 Hint

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

For n elements, bitmask runs from 0 to 2^n - 1, so total subsets are 2^n = 16 for n=4.

🔧 Debug

advanced

Identify the error in bitmask subset generation

What error will this code produce when generating subsets using bitmask?

DSA Python

nums = [1, 2, 3]
n = len(nums)
subsets = []
for mask in range(1 << n):
    subset = []
    for i in range(n):
        if mask & i:
            subset.append(nums[i])
    subsets.append(subset)
print(subsets)

A TypeError

B Wrong output subsets

C No error, correct output

D SyntaxError

💡 Hint

Check the condition mask & i carefully.

The condition mask & i is incorrect because i is an index, not a bitmask. It should be mask & (1 << i). This causes wrong subsets to be generated.

🧠 Conceptual

advanced

Understanding bitmask subset generation order

In what order are subsets generated by bitmask from 0 to 2^n - 1?

A Subsets are generated randomly

B Subsets are generated in lexicographical order of elements

C Subsets are generated in order of bitmask integer value from 0 to 2^n - 1

D Subsets are generated in increasing order of subset size

💡 Hint

Think about how the loop runs from 0 to 2^n - 1.

The subsets correspond to bitmask values from 0 to 2^n - 1, so they are generated in numeric order of the bitmask integer.

❓ Predict Output

expert

Find subset with maximum sum using bitmask

Given nums = [3, 1, 4, 2], which subset generated by bitmask has the maximum sum less than or equal to 6?

DSA Python

nums = [3, 1, 4, 2]
max_sum = 0
best_subset = []
n = len(nums)
for mask in range(1 << n):
    subset = []
    total = 0
    for i in range(n):
        if mask & (1 << i):
            subset.append(nums[i])
            total += nums[i]
    if total <= 6 and total > max_sum:
        max_sum = total
        best_subset = subset
print(best_subset)

A [1, 4, 2]

B [4, 2]

C [3, 4]

D [3, 1, 2]

💡 Hint

Check sums of subsets and find the largest sum <= 6. Note the update condition is strict greater than.

The code updates best_subset only when total > max_sum and total <=6. Subsets with sum=6 are [3,1,2] (mask=11, first sets max_sum=6) and [4,2] (mask=12, equal so no update). [1,4,2] sums to 7 >6. Thus, output is [3,1,2].

Practice

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

easy

A. Only subsets with odd number of elements

B. Only the largest subset of the set

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 a bitmask represents whether an element is included (1) or excluded (0) in a subset.

2. Step 2: Generate subsets using bitmask

   By iterating from 0 to 2^n - 1 (where n is number of elements), all combinations of included/excluded elements are covered, producing all subsets.

3. Final Answer:

   All possible subsets of the set -> Option D

4. Quick Check:

   Bitmask = subsets generator [OK]

Hint: Bitmask bits map directly to subset inclusion [OK]

Common Mistakes:

• Thinking bitmask generates only large subsets
• Confusing bitmask with sorting or filtering
• Assuming bitmask generates only even or odd subsets

2. Which of the following is the correct Python syntax to iterate over all bitmasks for a set of size n?

easy

A. for mask in range(1 << n):

B. for mask in range(n << 1):

C. for mask in range(2 * n):

D. for mask in range(n ** 2):

Solution

1. Step 1: Understand bit shift for 2^n

   Using 1 << n shifts 1 left by n bits, which equals 2 to the power n.

2. Step 2: Use range to cover all bitmasks

   Iterating from 0 to 1 << n - 1 covers all subsets represented by bitmasks.

3. Final Answer:

   for mask in range(1 << n): -> Option A

4. Quick Check:

   1 << n = 2^n range [OK]

Hint: Use 1 << n for 2^n subsets [OK]

Common Mistakes:

• Using multiplication instead of bit shift
• Using n squared or doubled incorrectly
• Confusing range limits

3. What is the output of the following code?

arr = ["a", "b"]
subsets = []
for mask in range(1 << len(arr)):
    subset = []
    for i in range(len(arr)):
        if mask & (1 << i):
            subset.append(arr[i])
    subsets.append(subset)
print(subsets)

medium

A. [['a', 'b'], ['a'], ['b'], []]

B. [[], ['a'], ['b'], ['a', 'b']]

C. [[], ['b'], ['a'], ['b', 'a']]

D. [['a'], ['b'], ['a', 'b'], []]

Solution

1. Step 1: Understand bitmask iteration

   For arr of length 2, masks go from 0 to 3 (00, 01, 10, 11 in binary).

2. Step 2: Map bits to elements

   Mask 0 (00) -> no elements -> [] Mask 1 (01) -> include arr[0] -> ['a'] Mask 2 (10) -> include arr[1] -> ['b'] Mask 3 (11) -> include arr[0], arr[1] -> ['a', 'b']

3. Final Answer:

   [[], ['a'], ['b'], ['a', 'b']] -> Option B

4. Quick Check:

   Bitmask subsets match output [OK]

Hint: Trace bitmask bits to elements included [OK]

Common Mistakes:

• Mixing order of subsets
• Appending elements incorrectly
• Confusing bit positions

4. Identify the error in the following code snippet for generating subsets using bitmask:

arr = [1, 2, 3]
subsets = []
for mask in range(1 << len(arr)):
    subset = []
    for i in range(len(arr)):
        if mask & i:
            subset.append(arr[i])
    subsets.append(subset)
print(subsets)

medium

A. The subset list should be initialized outside the loop

B. The range should be 'range(len(arr))' instead of 'range(1 << len(arr))'

C. The condition should be 'mask & (1 << i)' instead of 'mask & i'

D. The print statement should be inside the inner loop

Solution

1. Step 1: Analyze bitmask condition

   The condition 'mask & i' incorrectly checks bits; it should check if the i-th bit is set using 'mask & (1 << i)'.

2. Step 2: Correct bit checking

   Using 'mask & (1 << i)' correctly tests if the bit at position i is 1, indicating inclusion of arr[i].

3. Final Answer:

   The condition should be 'mask & (1 << i)' instead of 'mask & i' -> Option C

4. Quick Check:

   Bit check needs shift [OK]

Hint: Use bit shift to check bits, not index alone [OK]

Common Mistakes:

• Using 'mask & i' instead of 'mask & (1 << i)'
• Initializing subset outside loop causing accumulation
• Misplacing print inside loops

5. Given a list arr = [1, 2, 2], what is the output of the following code that generates subsets using bitmask?

arr = [1, 2, 2]
subsets = []
for mask in range(1 << len(arr)):
    subset = []
    for i in range(len(arr)):
        if mask & (1 << i):
            subset.append(arr[i])
    subsets.append(subset)
print(subsets)

hard

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

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

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

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

Solution

1. Step 1: Calculate total subsets

   For 3 elements, total subsets = 2^3 = 8, masks from 0 to 7.

2. Step 2: Map each mask to subset

   Mask 0 (000): [] Mask 1 (001): [1] Mask 2 (010): [2] (second element) Mask 3 (011): [1, 2] Mask 4 (100): [2] (third element) Mask 5 (101): [1, 2] Mask 6 (110): [2, 2] Mask 7 (111): [1, 2, 2]

3. Final Answer:

   [[], [1], [2], [1, 2], [2], [1, 2], [2, 2], [1, 2, 2]] -> Option A

4. Quick Check:

   Duplicates appear as separate elements [OK]

Hint: Duplicates create repeated subsets with same elements [OK]

Common Mistakes:

• Assuming duplicates merge subsets
• Missing subsets with repeated elements
• Incorrect mask to subset mapping