# 0797. All Paths From Source to Target
###### tags: `Leetcode` `Medium` `FaceBook` `DFS` `Backtracking`
Link: https://leetcode.com/problems/all-paths-from-source-to-target/
## 思路 O(2^(N)*N) O(N)
简单的backtracking基础题
暴搜~
由于给定的 graphgraph 为有向无环图（拓扑图），因此按照第 x−1 位置的值去决策第 x 位的内容，必然不会决策到已经在当前答案的数值，否则会与 graphgraph 为有向无环图（拓扑图）的先决条件冲突。所以不需要用visited判断该点是否有搜寻过

时间复杂度算法：
空间复杂度算法：（如果计算output的空间的话，是跟时间复杂度一样）

其实也可以用dp的方法解
但时间复杂度和空间复杂度是没变的，因此对于每条路径来说都要copy N 遍

## Backtracking 模板

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

## Code

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        result = []

        def dfs(start, currPath: List[int]):
          if start==len(graph)-1:
            result.append(copy.deepcopy(currPath))
            return
          for i in graph[start]:
            currPath.append(i)
            dfs(i, currPath)
            currPath.pop()

        dfs(0, [0])
        return result

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> curr = new ArrayList<>();
        curr.add(0);
        dfs(0, res, curr, graph);
        return res;
    }
    public void dfs(int u, List<List<Integer>> res, List<Integer> curr, int[][] graph){
        if(u == graph.length-1){
            res.add(new ArrayList<>(curr));
            return;
        }
        else{
            for(int v:graph[u]){
                curr.add(v);
                dfs(v, res, curr, graph);
                curr.remove(curr.size()-1);
            }
        }
    }
}