SOS DP - Transition

To compute $dp[\text{mask}][i]$, consider bit $i$ of mask:

$1.$ If bit $i$ is $0$ in mask: submasks must also have bit $i = 0$. So $dp[\text{mask}][i] = dp[\text{mask}][i-1]$. Nothing new to add.

$2.$ If bit $i$ is $1$ in mask: submasks can have bit $i$ as $0$ or $1$. Those with bit $i = 1$ contribute $dp[\text{mask}][i-1]$. Those with bit $i = 0$ contribute $dp[\text{mask} \oplus 2^i][i-1]$ (flip bit $i$ off). Combined: $dp[\text{mask}][i] = dp[\text{mask}][i-1] + dp[\text{mask} \oplus 2^i][i-1]$ when bit $i$ is set.