leetcode | go | 第797题 | 所有可能的路径

所有可能的路径

go

解决思路

1. n 设为 graph 的长度，即节点个数
2. ans 设为二维 int 数组，path 设为初值为 0 的  int 数组
3. dfs 没有参数也没有返回值
4. 如果 path 的最后一个值为 n-1，将 path 复制到新数组里然后加入 ans，return
5. 遍历 path 的最后一个值的相邻节点，即 graph[path[len(path)-1]（当前值为 site），将 site 加入 path，dfs()，然后回溯
6. dfs()；return ans
7. 题解思路：（1）深度优先搜索

相关问题

1. 好像有重复的路径，所以应该怎么去重呢
2. 虽然不知道为什么用深度优先搜索是对的，广度优先搜索就会出现重复

func allPathsSourceTarget(graph [][]int) [][]int {
    n:=len(graph)
    ans:=[][]int{}
    path:=[]int{0}
    var dfs func()
    dfs=func() {
        if path[len(path)-1]==n-1  {
            ans=append(ans,append([]int{},path...))
            return 
        }
        for _,site:=range graph[path[len(path)-1]] {
            path=append(path,site)
            dfs()
            path=path[:len(path)-1]
        }
    }
    dfs()
    return ans 
}