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 ? There are exactly two subsets for n=1 namely and , four subsets for n=2, and eight subsets for n=3. Since each new element doubles the number of possibilities, there are subsets of n elements.

Each subset is described by stating which elements are in it. Therefore, to construct all subsets, we can set up an array/vector of n cells, where the value of 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, , and A is a solution whenever .

Using this state space representation, the backtracking algorithm constructs the following sequence of partial solutions in finding the subsets of . 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 .

Algorithms
Mon Jun 2 23:33:50 EDT 1997