https://leetcode.com/problems/all-paths-from-source-to-target

First thing we need to notice, when we see this problem, that number of nodes is very small, it is in [2,15] range. It usually means, that we need to implement some bruteforce algorighm. What is also given, that our graph do not have any loops, which will make our life easier. Let us use function dfs(formed), where formed is path created so far.

  1. We need to stop and add formed to list of solutions sol if we reached the target.
  2. If we did not reach it, then for all children of last element, we run dfs(formed + [child]).
  3. Finally, we run our dfs function for dfs([0]).

Complexity: Let us consider the case of graph on n nodes, where any node from i to j exists, where i<j. For example for n=4, we have graphs = [[1,2,3,4],[2,3,4],[3,4],[4],[]]. How many paths we have it his case? It is exactly 2^(n-1), because for any number from 1 to n-1 you can either visit this node or not. For n=4 we have the following pathes: [0,4],[0,1,4],[0,2,4],[0,3,4],[0,1,2,4],[0,1,3,4],[0,2,3,4],[0,1,2,3,4]. Also for each path has in average O(n) elements. So, overall time and space complexity in this case is O(n 2^n).

Further improvements The main problem of this method is that is we have some dead-end, we do extra-job, checking options, which can not lead to success. I think, one possible improvement is to do topological sort of our data first and try to remove dead-ends, but I am not sure.

class Solution:
    def allPathsSourceTarget(self, graph):  
        def dfs(formed):
            if formed[-1] == n - 1:
                sol.append(formed)
                return      
            for child in graph[formed[-1]]:
                dfs(formed + [child])
                
        sol, n = [], len(graph)            
        dfs([0])
        return sol

If you like the solution, you can upvote it on leetcode discussion section: Problem 0797