# C# – How to find all possible subsets of a given array

algorithmc++

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.

#### Best Solution

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.