# All Paths From Source To Target

• @awice you can improve the time complexity to 2^N by only appending to the path.
Solution in short:

1. Change signature of solve to solve(graph, currentNodeIdx, path, ans)
2. Run solve like the following from allPathsSourceTarget: solve(graph, 0, [0], [])
3. Inside solve check that currentNodeIdx == len(graph) - 1, add path to ans then and return
4. If currentNodeIdx != len(graph) - 1, iterate over graph[currentNodeIdx] and inside the loop append instead of prepending, recurse and then pop back.

• I did this using 3 stacks

• DFS, Java, 11ms

``````class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
int n = graph.length;
Map<Integer, List<Integer>> g = new HashMap<>();

for (int i = 0; i < n; i++) {
if (!g.containsKey(i))
g.put(i, new ArrayList<>());

for (int j = 0; j < graph[i].length; j++)
}

List<List<Integer>> res = new ArrayList<>();
boolean[] used = new boolean[n];
List<Integer> path = new ArrayList<>();

used[0] = true;

dfs(0, n - 1, used, g, path, res);

return res;
}

private void dfs(int v, int end, boolean[] used, Map<Integer, List<Integer>> g, List<Integer> path, List<List<Integer>> res) {
if (v == end) {
return;
}

List<Integer> next = g.get(v);
if (next == null)
return;

for (int x : next) {
if (!used[x]) {
used[x] = true;
dfs(x, end, used, g, path, res);
path.remove(path.size() - 1);
used[x] = false;
}
}
}
}

``````

• class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> resultList = new ArrayList<>();
List<Integer> tempList = new ArrayList<>();
dfs(graph, 0, tempList, resultList);
return resultList;
}

``````public void dfs(int[][] graph, int start, List<Integer> tempList, List<List<Integer>> resultList) {
// 到达终点
if(start == graph.length - 1) {
// 加到集合里面
return;
}
// 不存在路径
if(graph[start].length == 0) {
return;
}
int len = tempList.size();
for(int i = 0; i < graph[start].length; i ++) {
// 复制集合，保留现场，便于下一个循环使用
List<Integer> subList = new ArrayList<>();
for (int j = 0; j < len; j++) {
}
dfs(graph, graph[start][i], subList, resultList);
}
}
``````

}

• Can you tell me why can there be O(2^N) paths?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.