next up previous contents index CD CD Algorithms
Next: Constructing All Permutations Up: Backtracking Previous: Backtracking

Constructing All Subsets

To design a suitable state space for representing a collection of combinatorial objects, it is important to know how many objects you will need to represent. How many subsets are there of an n-element set, say the integers tex2html_wrap_inline25663 ? There are exactly two subsets for n=1 namely tex2html_wrap_inline25667 and tex2html_wrap_inline25669 , four subsets for n=2, and eight subsets for n=3. Since each new element doubles the number of possibilities, there are tex2html_wrap_inline25675 subsets of n elements.  

Each subset is described by stating which elements are in it. Therefore, to construct all tex2html_wrap_inline25677 subsets, we can set up an array/vector of n cells, where the value of tex2html_wrap_inline25679 is either true or false, signifying whether the ith item is or is not in the given subset. To use the notation of the general backtrack algorithm, tex2html_wrap_inline25681 , and A is a solution whenever tex2html_wrap_inline25683 .

Using this state space representation, the backtracking algorithm constructs the following sequence of partial solutions in finding the subsets of tex2html_wrap_inline25685 . Final solutions, i.e. complete subsets, are marked with a *. False choices correspond to dashes in the partial solution, while true in position i is denoted by i itself:


Trace through this example carefully to make sure you understand the backtracking procedure. The problem of generating subsets is more thoroughly discussed in Section gif.

Mon Jun 2 23:33:50 EDT 1997