811. Shortest Path Visiting All Nodes (Recursion + Bitmask)

Given an undirected graph as adjacency list (graph[i] = neighbors of i), return the length of the shortest path that visits every node at least once. You may start from any node and revisit nodes/edges. Return -1 if impossible (disconnected). Input: JSON adjacency list.

Input: JSON adjacency list.

Output: Integer.

Examples

Input: [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: Start at 0, visit 1,2,3 (backtrack needed).

Input: [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: Path 0->1->2->3, then 2->4, total 4 edges.

Constraints

• 1 <= n <= 12

Asked by