题意

给定一个有n个节点的有向无环图（DAG），标签从0到n - 1，找到从节点0到节点n - 1的所有可能路径，并按任何顺序返回。

图是这样给出的：graph[i]是一个你可以从节点i访问的所有节点的列表（即，有一条从节点i到节点graph[i][j]的有向边）。

思路

这道题通过dfs可以解决，从0节点出发，当到达n-1的节点后，记录路径。

解题代码

func allPathsSourceTarget(graph [][]int) [][]int {
	ans := make([][]int, 0)
	var dfs func(int, []int)
	dfs = func(node int, path []int) {
		if node == len(graph)-1 {
			dst := make([]int, len(path))
			copy(dst, path)
			ans = append(ans, dst)
			return
		}

		for _, relNode := range graph[node] {
			dfs(relNode, append(path, relNode))
		}
	}
	dfs(0, []int{0})
	return ans
}