# 797. All Paths From Source to Target 所有可能的路径

@TOC

## # 题目描述

Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows: the nodes are 0, 1, ..., graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:

``````Input: [[1,2], [3], [3], []]
Output: [[0,1,3],[0,2,3]]

Explanation: The graph looks like this:

0--->1
|    |
v    v
2--->3

There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
``````

Note:

• The number of nodes in the graph will be in the range [2, 15].
• You can print different paths in any order, but you should keep the order of nodes inside one path.

## # 解题方法

### # 回溯法

``````class Solution(object):
def allPathsSourceTarget(self, graph):
"""
:type graph: List[List[int]]
:rtype: List[List[int]]
"""
res = []
self.dfs(graph, res, 0, [0])
return res

def dfs(self, graph, res, pos, path):
if pos == len(graph) - 1:
res.append(path)
return
else:
for n in graph[pos]:
self.dfs(graph, res, n, path + [n])
``````

``````class Solution(object):
def allPathsSourceTarget(self, graph):
"""
:type graph: List[List[int]]
:rtype: List[List[int]]
"""
res = []
self.dfs(graph, 0, len(graph) - 1, res, [0])
return res

def dfs(self, graph, start, end, res, path):
if start == end:
res.append(path)
for node in graph[start]:
self.dfs(graph, node, end, res, path + [node])
``````

``````class Solution {
public:
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<int> path;
path.push_back(0);
dfs(graph, 0, graph.size() - 1, path);
return res;
}
private:
vector<vector<int>> res;
void dfs(vector<vector<int>>& graph, int start, int end, vector<int> path) {
if (start == end) {
res.push_back(path);
} else {
for (int node : graph[start]) {
path.push_back(node);
dfs(graph, node, end, path);
path.pop_back();
}
}
}
};
``````

## # 日期

2018 年 3 月 20 日 ————阳光明媚～ 2018 年 12 月 2 日 —— 又到了周日