 Subset dynamic programming for a Hamiltonian path

For a directed graph with adjacency matrix $A$, let $D[S,v]$ record whether a path visits precisely the vertices of $S$ once and ends at $v$. The singleton states are true. A larger state is true exactly when some predecessor $u\in S\setminus \{v\}$ has a true state for $S\setminus \{v\}$ and an edge to $v$. Removing or adjoining the last edge proves this recurrence by mathematical induction on $|S|$. There are $n{2}^{n-1}$ states, each requiring at most $n-1$ predecessor checks, giving $O(n^2{2}^n)$ time and $O(n{2}^n)$ storage. A true state for $S=V$ certifies a Hamiltonian path.