PreviousNext
Coding/Dynamic programming

Count Hamiltonian paths

Write codeHard35 min

Your task

Given the adjacency matrix 'adj' of a directed graph on n nodes (adj[u][v] == 1 means there is an edge u to v), count the number of distinct Hamiltonian paths that start at node 0 and visit every node exactly once. Return the count. 1 <= n <= 14. A single node trivially has one path.

Examples

hamiltonian_path_count(adj: list[list[int]]) -> int
Example 1
Inputhamiltonian_path_count([[0, 1, 1], [1, 0, 1], [1, 1, 0]])
Output2