Approach #1: Recursion [Accepted]

Intuition

Since the graph is a directed, acyclic graph, any path from A to B is going to be composed of A plus a path from any neighbor of A to B. We can use a recursion to return the answer.

Algorithm

Let N be the number of nodes in the graph. If we are at node N-1, the answer is just the path {N-1}. Otherwise, if we are at node node, the answer is {node} + {path from nei to N-1} for each neighbor nei of node. This is a natural setting to use a recursion to form the answer.

Complexity Analysis

  • Time Complexity: . We can have exponentially many paths, and for each such path, our prepending operation path.add(0, node) will be .

  • Space Complexity: , the size of the output dominating the final space complexity.


Analysis written by: @awice.