我正在嘗試在Go中使用Leetcode 747。問題摘要:給定一個有向無環圖 (DAG),其中包含從 0 到 n - 1 的 n 個節點,找到從節點 0 到節點 n - 1 的所有可能的路徑,并按任意順序返回它們。圖給出如下:graph[i]是您可以從節點i訪問的所有節點的列表(即,從節點i到節點圖[i][j]有一個有向邊)。到目前為止,這是我的解決方案:func allPathsSourceTarget(graph [][]int) [][]int { allSolutions := [][]int{} target := len(graph) - 1 isSolution := func(current int) bool { return current == target } processSolution := func(solution []int) { allSolutions = append(allSolutions, solution) } var backtrack func(currentPath []int) backtrack = func(a []int) { currentNode := a[len(a)-1] if isSolution(currentNode) { processSolution(a) } else { candidates := graph[currentNode] for _, c := range candidates { a = append(a, c) backtrack(a) a = a[:len(a)-1] } } } backtrack([]int{0}) return allSolutions}它傳遞7/30輸入,但隨后在此輸入上失敗。其預期輸出為 。[[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]]我認為問題在于如何將每個結果附加到切片。如果我每次都記錄進來的解決方案,這是預期的,但它似乎會改變已經添加的解決方案。allSolutions如果我將日志添加到函數中,對于上述輸入,這是輸出:allSolutionsSolution:[0 4]New allSolutions:[[0 4]]Solution:[0 3 4]New allSolutions:[[0 3] [0 3 4]]Solution:[0 1 3 4]New allSolutions:[[0 1] [0 3 4] [0 1 3 4]]Solution:[0 1 2 3 4]New allSolutions:[[0 1] [0 3 4] [0 1 2 3] [0 1 2 3 4]]Solution:[0 1 4]New allSolutions:[[0 1] [0 3 4] [0 1 4 3] [0 1 2 3 4] [0 1 4]]我很想知道為什么會發生這種情況。它是否與從更高范圍修改變量有關?
在 Go 中回溯以查找有向無環圖中的所有路徑,為解切片分配路徑時出現問題
ibeautiful
2022-08-09 16:55:07