Enumerating Combinations Using BitSets
As an example of a problem that is easily solved with recursion and associated with solution sets that are very large, I've used the problem of enumerating all combinations of size N out of a set of size M. In Java, the cleanest way I can think of to solve this problem is to use java.util.BitSet.
A BitSet is essentially a vector of bits, each of which can be either set or unset at any given point. Such a structure is ideal for representing combinations and other subsets of items. If you consider an arbitrary subset of items from an underlying set, you can represent this subset as a BitSet with a length that is the same as the number of items in the underlying set. The original set is given an order, and every item in the underlying set has a corresponding bit in the BitSet. The subset that the BitSet represents contains all items that have their corresponding bit "on" and excludes all items that have their corresponding bit "off."
BitSets thus yield a simple way of enumerating all possible, exponentially many groups of items out of a given set. The problem of enumerating all combinations of N items out of a set of size M becomes, then, a problem of finding all BitSets of size M with exactly N "on" bits.
Consider the set with three elements. The three combinations of size 1 out of this set would be represented as BitSets corresponding to 001, 010, and 100. Combinations of size 2 would be represented as 011, 101, and 110.
A trivial solution to the problem of listing combinations would be to enumerate in numerical order all possible BitSets of length M and throw away all those that do not contain exactly N bits. This is wasteful, however; the solution in Example 1, which essentially prunes the tree — eliminating all enumerations that cannot yield successful results because they already contain enough "on" bits — should run faster.
— S.B.
