Generate all possible sub-set sum

bit-masking.cpp

#include <iostream>

using namespace std;

//Given an array, generate all possible sum

int main(void)
{

    int array[]= {1,2,3};
    int N= sizeof(array)/sizeof(int);

    for(int mask=0; mask < 1<<N; mask++) //generate numbers from 0 to 2^N-1.
        //Number of subsets for a N-length set = 2^N (including the empty set)
    {
        int sum=0;
        //Suppose that mask=6, in binary: 6 = 110
        //The for-loop below works like this:
        //check 0th bit, it is 0 so, no action, sum=0
        //check 1st bit, it is 1, so add array[1] to sum
        //check 2nd bit, it is 1, so add array[2] to sum
        //ultimately, sum = 0 + array[1] + array[2]

        //similarly, for 7=111
        //all bits are set
        //so, sum= array[0] + array[1] + array[2]

        //N= number of elements in the array = number of bits of mask that should be checked

        for(int i=0; i<N; i++ ) //check each bit of mask
        {
            if(mask & (1<<i)) //if the i-th bit is set, then add it to sum
            {
                sum+=array[i];
            }
        }
        cout<<sum<<endl;
    }
}