I am attempting Leetcode 747 in Go. The problem summary:
Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1, and return them in any order.
The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).
This is my solution so far:
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
}
It passes 7/30 inputs but then fails on this one [[4,3,1],[3,2,4],[3],[4],[]]. The expected output for which is [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]].
I believe the problem is how I am appending each result to the allSolutions slice. If I log the solution that comes in each time, it's what is expected, but it seems to then mutate the solutions already added.
If I add logs to the allSolutions func, for the above input, this is the output:
Solution:
[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]]
I am interested in knowing why this is happening. Is it related to modifying the variable from a higher scope?
processSolution should copy its argument. Otherwise, backtrack continues to mutate the slice that it passes in, which results in the corruption that you're seeing.