about bitmask and subset Dynamic Programming

It is all too common to use bitmask 0 to 1<<n -1 to represent all subsets of {1,...,n} and do some calculation on each subset. Now if your DP algorithm requires subsets be computed before their supersets, what do you do?

Ideally you would like to generate all subsets in the order of empty set, all {i}, then all {i,j}, ... However this might not be easy to implement, in particular, the 0,1,2,3,... subsets do not assume that order. Still you would like to do calculation use that order, that is, you compute dp[0], then dp[1], dp[2], dp[3], ... up to dp[(1<<n)-1]

You can use dp[s] = sum { for each j in s, dp[s^1<<j] }

Why, because s excludes j, that is s^1<<j is always a smaller integer than s. So even though the subsets are not generated in the order of size, they still guarantee subsets generated before super sets.