All Paths From Source to Target

LeetCode 797 · View on LeetCode

Find all paths from node 0 to node n-1 in a DAG. The graph is given as an adjacency list: graph[i] lists neighbors of node i. No visited set needed — it's a DAG (no cycles).

DFS Backtracking (memory efficient)

Reuses one path slice, only copies when a complete path is found.

package main

import "fmt"

func allPathsSourceTarget(graph [][]int) [][]int {
	result := [][]int{}
	path := []int{0}

	var dfs func(node int)
	dfs = func(node int) {
		if node == len(graph)-1 {
			result = append(result, append([]int{}, path...))
			return
		}
		for _, nei := range graph[node] {
			path = append(path, nei)
			dfs(nei)
			path = path[:len(path)-1] // backtrack
		}
	}

	dfs(0)
	return result
}

func main() {
	graph := [][]int{{1, 2}, {3}, {3}, {}}
	fmt.Println(allPathsSourceTarget(graph)) // [[0 1 3] [0 2 3]]
}

BFS with Path Tracking

Each queue entry stores an entire path. Simpler logic but copies the path at every step.

package main

import "fmt"

func allPathsSourceTarget(graph [][]int) [][]int {
	result := [][]int{}
	queue := [][]int{{0}}

	for len(queue) > 0 {
		path := queue[0]
		queue = queue[1:]
		node := path[len(path)-1]
		if node == len(graph)-1 {
			result = append(result, path)
			continue
		}
		for _, nei := range graph[node] {
			newPath := make([]int, len(path)+1)
			copy(newPath, path)
			newPath[len(path)] = nei
			queue = append(queue, newPath)
		}
	}
	return result
}

func main() {
	graph := [][]int{{1, 2}, {3}, {3}, {}}
	fmt.Println(allPathsSourceTarget(graph)) // [[0 1 3] [0 2 3]]
}

Comparison

	DFS Backtracking	BFS Path Tracking
Memory	O(depth) for path + O(results)	O(all paths × avg length) in queue
Style	Recursive, reuses one slice	Iterative, copies at every step
When	Preferred — less allocation	When you need shortest paths first