題目

給一個有 n 個結點的有向無環圖，找到所有從 0 到 n-1 的路徑並輸出（不要求按順序）

二維陣列的第 i 個數組中的單元都表示有向圖中 i 號結點所能到達的下一些結點

（譯者注：有向圖是有方向的，即規定了 a→b 你就不能從 b→a ）空就是沒有下一個結點了。

示例 1：輸入：graph = [[1,2],[3],[3],[]] 輸出：[[0,1,3],[0,2,3]]

解釋：有兩條路徑 0 -> 1 -> 3 和 0 -> 2 -> 3

示例 2：輸入：graph = [[4,3,1],[3,2,4],[3],[4],[]]

輸出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

示例 3：輸入：graph = [[1],[]] 輸出：[[0,1]]

示例 4：輸入：graph = [[1,2,3],[2],[3],[]] 輸出：[[0,1,2,3],[0,2,3],[0,3]]

示例 5：輸入：graph = [[1,3],[2],[3],[]] 輸出：[[0,1,2,3],[0,3]]

提示：結點的數量會在範圍 [2, 15] 內。

你可以把路徑以任意順序輸出，但在路徑內的結點的順序必須保證。

1、回溯；時間複雜度O(2^n*n^2)，空間複雜度O(2^n*n)

var res [][]intfunc allPathsSourceTarget(graph [][]int) [][]int {	res = make([][]int, 0)	dfs(graph, 0, len(graph)-1, make([]int, 0))	return res}func dfs(graph [][]int, cur, target int, path []int) {	if cur == target {		path = append(path, cur)		temp := make([]int, len(path))		copy(temp, path)		res = append(res, temp)		return	}	for i := 0; i < len(graph[cur]); i++ {		dfs(graph, graph[cur][i], target, append(path, cur))	}}

Medium題目，有向無環圖，使用回溯探索所有可能路徑