Considering a set S
of N
elements, and a given subset, each element either does or doesn't belong to that subset. Therefore are 2^N
possible subsets (if you include the original and empty sets), and there is a direct mapping from the bits in the binary representation of x
between 0
and 2^N
to the elements in the x
th subset of S
.
Once you've worked out how to enumerate the elements of a given subset, adding the values is simple.
For finding subsets which equal a total t
for large N
, one optimisation might be to record those subsets which exceed t
, and not test any which are proper supersets of those. Testing whether set number x
is a superset of set y
can be achieved with a single bitwise operation and an integer comparison.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…