All Paths From Source to Target

medium graph dfs backtracking

Problem

Given a directed acyclic graph of n nodes (0 to n − 1) as adjacency lists, return all possible paths from node 0 to node n − 1 in any order.

Inputgraph = [[1,2],[3],[3],[]]

Output[[0,1,3],[0,2,3]]

Two routes from node 0 to node 3.

adjacency (rows ;, neighbors ,)

def all_paths_source_target(graph):
    n = len(graph)
    out = []
    path = [0]
    def dfs(u):
        if u == n - 1:
            out.append(path[:])
            return
        for v in graph[u]:
            path.append(v)
            dfs(v)
            path.pop()
    dfs(0)
    return out

function allPathsSourceTarget(graph) {
  const n = graph.length;
  const out = [];
  const path = [0];
  const dfs = (u) => {
    if (u === n - 1) { out.push(path.slice()); return; }
    for (const v of graph[u]) {
      path.push(v);
      dfs(v);
      path.pop();
    }
  };
  dfs(0);
  return out;
}

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int n = graph.length;
        List<List<Integer>> out = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        path.push(0);
        dfs(graph, 0, n - 1, path, out);
        return out;
    }
    private void dfs(int[][] g, int u, int target, Deque<Integer> path, List<List<Integer>> out) {
        if (u == target) {
            List<Integer> copy = new ArrayList<>(path);
            Collections.reverse(copy);
            out.add(copy);
            return;
        }
        for (int v : g[u]) {
            path.push(v);
            dfs(g, v, target, path, out);
            path.pop();
        }
    }
}

class Solution {
public:
    vector<vector<int>> out;
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> path = {0};
        dfs(graph, 0, n - 1, path);
        return out;
    }
    void dfs(vector<vector<int>>& g, int u, int target, vector<int>& path) {
        if (u == target) { out.push_back(path); return; }
        for (int v : g[u]) {
            path.push_back(v);
            dfs(g, v, target, path);
            path.pop_back();
        }
    }
};

Explanation

We want every route from node 0 to node n-1, so we explore the graph with DFS plus backtracking, building up the current path as we go and saving a copy each time we arrive at the target.

The list path always holds the nodes on the route we are currently walking. When the current node equals n-1, we have a complete path, so we push a copy of path into the answer (a copy, because path will keep changing).

The backtracking part is the pattern path.append(v); dfs(v); path.pop(). We add a neighbour, dive deeper, and after returning we remove it so we can cleanly try the next neighbour. Because the graph is a DAG, there are no cycles to worry about.

Example: graph = [[1,2],[3],[3],[]]. From 0 we try 0→1→3 (record [0,1,3]), backtrack, then 0→2→3 (record [0,2,3]), giving [[0,1,3],[0,2,3]].

Time: O(2ⁿ · n) Space: O(n)