How do you generate all subsets of a set, and what is the complexity of the result?
You build the subsets one item at a time, and for every item you make two choices. You either take it into the current subset or you leave it out.
So there are two ways to write it. The first one is with a bitmask, where every subset has a number that describes which items are in it. The second one is with recursion, where you keep a list of the items chosen so far and you add one more at a time.
def subsets(values):
result = []
for mask in range(1 << len(values)):
group = [values[i] for i in range(len(values)) if mask & (1 << i)]
result.append(group)
return result
And the size of the answer is the important fact here. A set of n items has 2 to the power of n subsets, because each item has two choices. So there are 16 subsets of four items, 32 of five, and 1024 of ten.
the items the subsets the time
----------- ------------- ------------------
1 2 2
4 16 16
10 1,024 1,024
20 1,048,576 about a million
So the complexity is O of n times 2 to the power of n for the time, and the same for the space, because there are 2 to the power of n subsets and each one holds up to n items. And that is not something you can make faster, because you have to produce all of them. The answer itself is that big.
And this is worth knowing about when an interview question asks for all the subsets. The number of subsets grows very fast, so on ten items the answer is a thousand lists and on twenty items it is over a million lists. So the interviewer is often really asking whether you can see the growth, and whether you would notice when the list of items is too big for the question to make sense.
So the rule to remember is this. The number of subsets is 2 to the power of n, and no algorithm can be faster than the size of the answer.
The last question in this topic shows the bitmask version in full.