= Solution
Use <subset dynamic programming for a Hamiltonian path>, with a Boolean <dynamic programming state> $D[S,v]$ for each nonempty <subset> $S\subseteq V$ and $v\in S$. It is true exactly when there is a <graph path> using every <vertex> of $S$ once, using no other <vertices>, and ending at $v$. The base and transition are
$$
D[\{v\},v]=\mathrm{true},\qquad
D[S,v]=\bigvee_{u\in S\setminus\{v\}}
\bigl(D[S\setminus\{v\},u]\land A[u,v]\bigr)
\quad(|S|\geq2),
$$
where $A$ is the <adjacency matrix of a directed graph>.
``
HamiltonianExists(A):
initialize every D[S,v] to false
for v in V:
D[{v},v] = true
for k = 2,...,n:
for S subset of V with |S| = k:
for v in S:
D[S,v] = any(D[S-{v},u] and A[u,v]
for u in S-{v})
return any(D[V,v] for v in V)
``
For correctness, a valid path ending at $v$ has some penultimate <vertex> $u$; removing $v$ yields exactly a path recorded by the corresponding predecessor state. Conversely, extending any true predecessor state by the edge $(u,v)$ produces a path visiting precisely $S$ once. <Mathematical induction> on $|S|$ proves the meaning of every state. Therefore \b[the final disjunction is true exactly when a <Hamiltonian path> exists].
There are $n2^{n-1}$ possible states and at most $n-1$ predecessor checks per state. More exactly, the full set of ordered predecessor checks has size $n(n-1)2^{n-2}$ for $n\geq2$. With constant-time <adjacency matrix> access and ordinary subset-indexed table access,
$$
\boxed{\text{time }O(n^2 2^n),\qquad\text{space }O(n2^n)}.
$$
The graph is normally assumed nonempty here. If the empty graph is admitted, return the chosen convention for its empty <Hamiltonian path> separately; it does not affect the bound.
Back to article page
