Subset Operations

When subsets are represented as bitmasks, set operations become bitwise operations:

• Union of sets $A$ and $B$: $A | B$ (OR combines both)

• Intersection of sets $A$ and $B$: $A \& B$ (AND keeps common elements)

• Difference $A - B$: $A \& (\sim B)$ (elements in $A$ but not in $B$)

• Check if element $i$ is in set $S$: $(S \& (1 << i)) \neq 0$

These operations run in $O(1)$ time when $n \leq 32$ or $n \leq 64$, making bitmask DP transitions run in $O(1)$ time.