//S = bitmask representation of available subset
//{1,2,3} ,S = 3 means only {2,3} are available since binary(3) = 0 1 1
for (int G = S; G != 0 ; G = (G - 1) & S)
This one liner generates subset of a subset in bit representation form. Would be grateful if anyone can give any intuition or explain the above line. Dont want to mug this up.
Eg: ~~~~~ The subset = 1110 The subsets of subset : 1110 1100 1010 1000 0110 0100 0010 ~~~~~
$$$G - 1$$$ remove rightmost set bit and make all other bit on the right side of it setted
$$$10010101000... \rightarrow 10010100111...$$$
$$$00010100000... \rightarrow 00010011111...$$$
But not all of the left-part on right-side are included in $$$S$$$. So by doing $$$(G - 1)$$$ & $$$S$$$, you removed the rightmost bit and turn on all other bit included in $$$S$$$ in right side
About the complexity. It is $$$O(3^n)$$$
1) Since $$$S$$$ is a bitmask and $$$G$$$ is a submask. Hence $$$G \subseteq S \Rightarrow \forall\ x \in G \rightarrow x \in S$$$. For each bit $$$x$$$, there are 3 cases
$$$\Rightarrow$$$ for $$$n$$$ bits, there are $$$O(3^n)$$$ cases
2) Each submask is a combination with $$$k$$$ set bit in $$$n$$$ total bits and for each combination there are $$$2^k$$$ submasks. Hence, the number of submasks are
$$$\overset{n}{\underset{k = 0}{\Sigma}} \binom{n}{k} \cdot 2^k = 3^n$$$