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].