<p>You have an undirected, connected graph of <code>n</code> nodes labeled from <code>0</code> to <code>n - 1</code>. You are given an array <code>graph</code> where <code>graph[i]</code> is a list of all the nodes connected with node <code>i</code> by an edge.</p>

<p>Return <em>the length of the shortest path that visits every node</em>. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/12/shortest1-graph.jpg" style="width: 222px; height: 183px;" />
<pre>
<strong>Input:</strong> graph = [[1,2,3],[0],[0],[0]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> One possible path is [1,0,2,0,3]
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/12/shortest2-graph.jpg" style="width: 382px; height: 222px;" />
<pre>
<strong>Input:</strong> graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> One possible path is [0,1,4,2,3]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == graph.length</code></li>
	<li><code>1 &lt;= n &lt;= 12</code></li>
	<li><code>0 &lt;= graph[i].length &lt;&nbsp;n</code></li>
	<li><code>graph[i]</code> does not contain <code>i</code>.</li>
	<li>If <code>graph[a]</code> contains <code>b</code>, then <code>graph[b]</code> contains <code>a</code>.</li>
	<li>The input graph is always connected.</li>
</ul>

class Solution:
    # implementation 1 using set, and step approach
    # def shortestPathLength(self, graph: List[List[int]]) -> int:
    #     queue = deque()
    #     visited_state = set()
    #     n = len(graph)

    #     # add to queue:
    #     for i in range(n):
    #         state = (i, 1 << i)
    #         queue.append((state, 0))
    #         visited_state.add(state)

    #     target = (1 << n) - 1
    #     while queue:
    #         state, step = queue.popleft()
    #         curr, visited = state
    #         if visited == target:
    #             return step
    #         for neigh in graph[curr]:
    #             new_state = (neigh, visited | (1 << neigh))
    #             if new_state in visited_state:
    #                 continue
    #             queue.append((new_state, step + 1))
    #             visited_state.add(new_state)
        
    #     return -1

    # implementation 2 using 2D visited array to track steps
    # each value in visited_state is the smallest number of step to get to the current node
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        queue = deque()
        n = len(graph)
        
        visited_state = [[0 for _ in range(2 ** n)] for _ in range(n)]

        for node in range(n):
            visited_state[node][1 << node] = 1
            queue.append((node, 1 << node))

        while queue:
            curr, visited_nodes = queue.popleft()
            if visited_nodes == (1 << n) - 1:
                return visited_state[curr][visited_nodes] - 1
            
            for neigh in graph[curr]:
                new_visited_nodes = visited_nodes | (1 << neigh)
                if visited_state[neigh][new_visited_nodes]:
                    continue
                visited_state[neigh][new_visited_nodes] = visited_state[curr][visited_nodes] + 1
                queue.append((neigh, new_visited_nodes))
        
        return -1
        

17600