Изменения
Замена d (из предыдущей части решения) на d' (в текущей)
d'[mask] = \left\{\begin{array}{llcl}
mask &;\ |mask| = 1 \\
\sum_{i \in [0..n-1] \& mask_i=1}\limits 2^i \cdot ((d'[mask \oplus 2^i] \& M_i) \neq 0?1:0) &;\ |mask| > 1 \\
0&;\ otherwise\\
\end{array}\right.
</tex>
Особое внимание следует уделить выражению <tex>d'[mask \oplus 2^i] \& M_i</tex> . Первая часть выражения содержит подмножество вершин, для которых существует гамильтонов путь, заканчивающихся в соответствующих вершинах в подмножестве <tex>mask</tex> без вершины <tex>i</tex>, а вторая — подмножество вершин, связанных с <tex>i</tex> ребром. Если эти множества пересекаются хотя бы по одной вершине (их <tex>\&</tex> не равен <tex>0</tex>), то, как нетрудно понять, в <tex>mask</tex> существует гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.
Окончательная проверка состоит в сравнении <tex>d'[2^n - 1]</tex> c <tex>0</tex>.
Это решение использует <tex>O(2^n)</tex> памяти и имеет асимптотику <tex>O(2^nn)</tex>.
