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 N1
, the answer is just the path {N1}
. Otherwise, if we are at node node
, the answer is {node} + {path from nei to N1}
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.