Hamiltonian Flights - Analysis

Pattern recognition:

• Visit every vertex exactly once = Hamiltonian path
• Count paths, not just existence
• $n \leq 20$ = bitmask DP is feasible

State: dp[mask][i] = number of paths visiting exactly the cities in $mask$, ending at city $i$.

Transition: For each edge $(i, j)$:

if mask has i and not j:
 dp[mask | (1 << j)][j] += dp[mask][i]

Answer: dp[2^n - 1][n-1] (all cities visited, ending at city $n$).