The learning goals of this lab are the following:
In this lab, you are asked to implement the two methods in the EnumeratingSubsets class.
allSubsets takes a set S and returns the powerset of S.allSubsetsOfSize takes a set S and an integer k and returns all subsets of S that have exactly k elements.The pencil and paper exercises from last time should help you in tackling these methods recursively.
Recursive implementation You are expected to implements each of these methods as recursive ones.
Test your work In the main method, you should call your methods on various examples to verify that they work correctly.
Efficiency considerations A simple but inefficient way to implement allSubsetsOfSize is to call allSubsets and then loop over the returned result, keeping only those sets of size k. But this is very inefficient, especially when k is near 0 or near the size of the set. Your implementation of allSubsetsOfSize should do something smarter.
Teaming up You may work with a partner. Larger groups are not permitted.
Implement both recursive and iterative versions of these methods.