To design a suitable state space for representing permutations, we start by counting them. There are n distinct choices for the value of the first element of a permutation of . Once we have fixed this value of , there are n-1 candidates remaining for the second position, since we can have any value except (repetitions are forbidden). Repeating this argument yields a total of distinct permutations.
This counting argument suggests a suitable representation. To construct all n! permutations, set up an array/vector A of n cells. The set of candidates for the ith position will be the set of elements that have not appeared in the (i-1) elements of the partial solution, corresponding to the first i-1 elements of the permutation. To use the notation of the general backtrack algorithm, . The vector A contains a full solution whenever k = n+1. This representation generates the permutations of in the following order:
The problem of generating permutations is more thoroughly discussed in Section .