What this is doing could be described this way.
- If originalSet is empty, then return
{}
(since the empty set's only subset is the empty set). - Split originalSet into the first element (
head
) and all the others (rest
). - We're keeping a running collection (
sets
) that will eventually be our answer. For every subset of originalSet that doesn't contain the first element (subsets ofrest
), put both it and a set which has all its elements plushead
into our collection.
Example for {1, 2, 3}
:
We want to find the power set of {1, 2, 3}.
In order to do this, we take off 1 and find the power set of {2, 3}.
In order to do this, we take off 2 and find the power set of {3}.
In order to do this, we take off 3 and find the power set of {}.
Which is {}.
For everything above ({}), copy it over, then copy it over but add a 3.
We have {{}, {3}}.
For everything above ({}, {3}), copy it over, then copy it over but add a 2.
We have {{}, {3}, {2}, {2, 3}}.
For everything above ({}, {3}, {2}, {2, 3}), copy it over, then copy it over but add a 1.
We have {{}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}}.
Note that there should always be 2^n
elements, where n
is the size of the original set.