I am studying for an interview and I stumbled upon this question online under the "Math" category.
Generate power set of given set:
int A[] = {1,2,3,4,5};
int N = 5;
int Total = 1 << N;
for ( int i = 0; i < Total; i++ ) {
for ( int j = 0; j < N; j++) {
if ( (i >> j) & 1 )
cout << A[j];
}
cout <<endl;
}
Please I do not want an explicit answer. I just want clarifications and hints on how to approach this problem.
I checked power set algorithm on google and I still do not understand how to address this problem.
Also, could someone reiterate what the question is asking for.
Thank you.
Power set of a set A is the set of all of the subsets of A.
Not the most friendly definition in the world, but an example will help :
Eg. for {1, 2}
, the subsets are : {}, {1}, {2}, {1, 2}
Thus, the power set is {{}, {1}, {2}, {1, 2}}
Let this decision be indicated by a bit (1/0).
Thus, to generate {1}
, you will pick 1
and drop 2
(10).
On similar lines, you can write a bit vector for all the subsets :
To reiterate : A subset if formed by including some or all of the elements of the original set. Thus, to create a subset, you go to each element, and then decide whether to keep it or drop it. This means that for each element, you have 2 decisions. Thus, for a set, you can end up with 2^N
different decisions, corresponding to 2^N
different subsets.
See if you can pick it up from here.