Heres a more direct way of nding the k-subsets of S. Like the power set algorithm from Problem 1, this one is recursive. Lets start with a specic example. Suppose we want to nd all 2-subsets of the set {x,y,z}.

Remove an arbitrary element from {x,y,z}. Lets say we remove the element x, so the set is now just {y,z}.

First, well consider the 2-subsets that do contain x. Find all 1-subsets of {y,z}: {y}, {z} Insert x into each of those 1-subsets: {x,y}, {x,z}

Now, well consider the 2-subsets that dont contain x. This just requires nding all the 2-subsets of {y,z}; theres only one of these (the set {y,z} itself).

Combine the 2-subsets from above to get the answer. In general, to nd the k-subsets of set S:

Remove an arbitrary element x S. S is now smaller by one element.

Consider the k-subsets that do contain x: nd all (k1)-subsets of S, and insert x into each of those subsets.

Consider the k-subsets that dont contain x: nd all k-subsets of S.

Combine the k-subsets from above to get the answer.

Write a Python function k subsets better(S, k) that uses the recursive algorithm presented above to return a set containing all the k-subsets of S. As before, represent the sets using Python lists. If k is not valid (i.e., negative, or greater than |S|), this function should return the empty list, [].