Sometimes, u need to enumerate all possible subsets of a size n as a
sub-problem of some bigger problem. This can be done using bitmasks (ie)
using bits of an integer to represent whether the element is there in
the current subset(bit is 'set' or 1) or it is not in the current
subset(bit is 'not set' or 0). C++ code with explanation follows:
int n=10; // size of set int n2=1<<n; // set of size n has 2^n subsets for(int i=1;i<n2;i++) { mask = i; pos=n-1; while(mask>0) { if((mask&1)==1) { // Element at pos belongs to the current subset. } mask>>=1; pos--; } }
No comments:
Post a Comment