Recall & Review
beginner
What is the main idea behind generating subsets using bitmask?
Each subset corresponds to a binary number where each bit represents whether an element is included (1) or excluded (0) from the subset.
Click to reveal answer
beginner
How many subsets can be generated from a set of size n using bitmask?
There are 2^n subsets because each element can either be included or excluded independently.
Click to reveal answer
intermediate
In C, how do you check if the i-th element is included in the subset represented by bitmask m?
Use the expression (m & (1 << i)) != 0 to check if the i-th bit is set, meaning the element is included.
Click to reveal answer
intermediate
Why is bitmasking an efficient way to generate subsets compared to recursion?
Bitmasking uses simple bit operations and loops, avoiding function call overhead and making it easy to generate all subsets iteratively.
Click to reveal answer
beginner
What is the output of subsets generated by bitmask for the set {a, b}?
The subsets are: {}, {a}, {b}, {a, b} corresponding to bitmasks 00, 01, 10, 11 respectively.
Click to reveal answer
How many subsets does a set with 3 elements have?
✗ Incorrect
A set with 3 elements has 2^3 = 8 subsets.
What does the bitmask 101 represent for a set {x, y, z}?
✗ Incorrect
Bitmask 101 means bits 0 and 2 are set, so elements x and z are included.
Which operation checks if the i-th bit is set in a bitmask m?
✗ Incorrect
The bitwise AND with (1 << i) checks if the i-th bit is set.
What is the total number of subsets for an empty set?
✗ Incorrect
An empty set has exactly one subset: the empty subset.
Which of these is NOT a subset of {1, 2}?
✗ Incorrect
{2, 3} is not a subset because 3 is not in the original set.
Explain how bitmasking helps generate all subsets of a set.
Think about how binary numbers can represent choices for each element.
You got /4 concepts.
Describe the steps to generate subsets of a set of size n using bitmask in C.
Focus on the loop and bit checking process.
You got /4 concepts.