Approach #1: Breadth First Search [Accepted]
Intuition
A path 'state' can be represented as the subset of nodes visited, plus the current 'head' node. Then, the problem reduces to a shortest path problem among these states, which can be solved with a breadthfirst search.
Algorithm
Let's call the set of nodes visited by a path so far the cover, and the current node as the head. We'll store the cover
states using set bits: k
is in the cover if the k
th bit of cover
is 1.
For states state = (cover, head)
, we can perform a breadthfirst search on these states. The neighbors are (cover  (1 << child), child)
for each child in graph[head]
.
If at any point we find a state with all set bits in it's cover, because it is a breadthfirst search, we know this must represent the shortest path length.
Complexity Analysis

Time Complexity: .

Space Complexity: .
Approach #2: Dynamic Programming [Accepted]
Intuition
A path 'state' can be represented as the subset of nodes visited, plus the current 'head' node. As in Approach #1, we have a recurrence in states: answer(cover, head)
is min(1 + answer(cover  (1<<child), child) for child in graph[head])
. Because these states form a DAG (a directed graph with no cycles), we can do dynamic programming.
Algorithm
Let's call the set of nodes visited by a path so far the cover, and the current node as the head. We'll store dist[cover][head]
as the length of the shortest path with that cover and head. We'll store the cover
states using set bits, and maintain the loop invariant (on cover
), that dist[k][...]
is correct for k < cover
.
For every state (cover, head)
, the possible next
(neighbor) nodes in the path are found in graph[head]
. The new cover2
is the old cover plus next
.
For each of these, we perform a "relaxation step" (for those familiar with the BellmanFord algorithm), where if the new candidate distance for dist[cover2][next]
is larger than dist[cover][head] + 1
, we'll update it to dist[cover][head] + 1
.
Care must be taken to perform the relaxation step multiple times on the same cover if cover = cover2
. This is because a minimum state for dist[cover][head]
might only be achieved through multiple steps through some path.
Finally, it should be noted that we are using implicitly the fact that when iterating cover = 0 .. (1<<N)  1
, that each new cover cover2 = cover  1 << x
is such that cover2 >= cover
. This implies a topological ordering, which means that the recurrence on these states form a DAG.
Complexity Analysis

Time Complexity: .

Space Complexity: .
Analysis written by: @awice.