Hamiltonian Path — Every Vertex Once (NP-Hard)

Backtracking

boolean hamiltonian(int u, boolean[] visited, int count) {
  if (count == n) return true;
  visited[u] = true;
  for (int v : graph[u]) if (!visited[v]) if (hamiltonian(v, visited, count + 1)) return true;
  visited[u] = false;
  return false;
}

Bitmask DP for TSP

dp[mask][v] = shortest path visiting nodes in mask ending at v. Transitions from dp[mask - v][u] + dist(u, v). O(2^N × N²).

Practical N

Backtracking works for N ≤ ~20 with good pruning. Bitmask DP: N ≤ ~22 in memory.

Special graphs

Bipartite: use Konig-Egerváry. Sparse cubic: Robertson–Sanders–Seymour–Thomas. Various special-case polys.