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 
.