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;
}Advertisement
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²).
Advertisement
Practical N
Backtracking works for N ≤ ~20 with good pruning. Bitmask DP: N ≤ ~22 in memory.