3

The brute force solution enumerates all permutations. You can easily encode each permutation using $n\log n$ bits, since you can encode it as a list of numbers from $1$ to $n$, and each number takes $\log n$ bits to encode. You can check that a given permutation corresponds to a tour using $O(\log n)$ additional bits of space, so in total the space ...


Only top voted, non community-wiki answers of a minimum length are eligible