Explain this code.

general
,
1

void printSubsequences(int arr[], int n)
{
unsigned int opsize = pow(2, n);

    for (int counter = 1; counter < opsize; counter++)
    {
        for (int j = 0; j < n; j++)
        {
            if (counter & (1<<j))
                cout << arr[j] << " ";
        }
        cout << endl;
    }
}
**This is algorithm for sub sequences**.
how sub sequences can be found by this ?
2

@gautamcse27 You must have understood that the total number of subsequences are 2^n and in each of subsequence there is at most n elements. Everytime we decide for each element to take that element or not. So total 2^n subsequences.

Now outer loop (i.e counter) runs from 1 to 2^n and we get every combination like for n=2 we get 01 00 11 10 and for each iteration of outer loop we go from 0 to n-1 [0,n-1] (inner loop) and take and 1<<j for this case n=2 so it will be 01 and 10 i.e (1<<0 and 1<<1).
So you can see that we are going through each possible unique set out of n values.Because we iterated through all possible sets (which is denoted by binary representation of 1 to 2^n values) and took and (&) with (0001,0010,0100,1000 ) say for n=4.
Hope this is clear.

3

This link, Bit Manipulation | HackerEarth should help.

2 Likes