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
*i*th 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 .

Mon Jun 2 23:33:50 EDT 1997