You get a connected, undirected graph with n nodes labelled 0..n-1 as an adjacency list: graph[u] lists the neighbours of u.
Write shortest_path_length(graph: list[list[int]]) -> int returning the number of edges in the shortest walk that visits every node at least once. You may start and finish at any node, and you may reuse nodes and edges as often as you like.
Constraints: 1 <= n <= 12, the graph is connected, no self-loops or duplicate edges.
# A star: centre 0 joined to 1, 2 and 3.
shortest_path_length([[1, 2, 3], [0], [0], [0]]) # 4, e.g. 1-0-2-0-3
# A path 0-1-2-3: just walk along it.
shortest_path_length([[1], [0, 2], [1, 3], [2]]) # 3
shortest_path_length([[]]) # 0 (one node, already visited)
Trying every visiting order (n!) is far too slow for n = 12; aim for about O(2^n · n²).
Show hint
Your current node alone doesn't describe how far along you are. Ask what else a state must remember, and notice that with n <= 12 there are only a few tens of thousands of such states. Since every edge costs 1, a breadth-first search over those states, started from every node at once, finds the shortest walk.