c# - How to find all possible subsets of a given array?

Question

I want to extract all possible sub-sets of an array in C# or C++ and then calculate the sum of all the sub-set arrays' respective elements to check how many of them are equal to a given number.

What I am looking for is the algorithm. I do understand the logic here but I have not been able to implement this one by now.

Answer 1

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 xth 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.