How to calculate all the subsets of an array?

Question

If I have array [1,2,3], I should get [1], [2], [3], [1,2],[2,3],[1,3].

Answer 1

Okay, here is the pseudo code for my favorite algorithm:

Input: Set[], set_size
1. Get the size of power set
powet_set_size = pow(2, set_size)
2 Loop for counter from 0 to pow_set_size
(a) Loop for i = 0 to set_size
(i) If ith bit in counter is set
Print ith element from set for this subset
(b) Print separator for subsets i.e., newline

I copied the pseudo code from a website where there is already a solution in java but I think you should try to implement it yourself first.

The idea of that algorithm is that if you take all binary numbers up to the size of the powerset (which is another name for all subsets of a set) and use the binary numbers as indicator of a subset, you get all possible subsets. For example:

set = (1,2,3)
number of subsets is 2^3 =8

First number in loop is 0 (which is 000 in binary if u take 3 places):

000 => () // empty set, no element is picked

Second number in loop is 1 (which is 001 in binary):

001 => (3) //take only the last number in the set

Third number in loop is 2:

010 => (2) // second element is picked

3:
011 => (2,3)
4:
100 =>(1)
5:
101 => (1,3)

and so on until you get to 7:

111 => (1,2,3)

When implementing the algorithm the only problematic feat is to determine if a certain place is a zero or a one. You can do that with a bitwise operator: if ((counter>>i)%2==1) {}

The algorithm is pretty hard to understand at first but afterwards you will admire the beauty of it. ;-)

Answer 2

The empty array and the "full" one are also subsets. That gives you 8 subsets in this case (2^n where n is the number of elements in the array).

There are several algorithms you could implement. Look for them online and choose one you feel comfortable with. If you can't find one, let me know and I'll show you one.

Answer 3

Thoq! Oh, please. Tell me the algorithms, that would be great.

Answer 4

Thoq! Nice. It's not hard to understand. It's the binary numbers and bitwise operator which do the trick. I didn't consider this. Thanks, man!