LeetCode 797. 所有可能的路径

Categories:

题目描述
思路分析
1. 解法一：DFS 回溯（推荐）
相似题目

题目描述

✅ 797. 所有可能的路径

思路分析

解法一：DFS 回溯（推荐）

核心思路：

从节点 0 出发 DFS，记录当前路径。

当到达终点 n-1 时加入结果。

回溯恢复路径继续搜索。

复杂度分析：

时间复杂度：O(路径数 * 路径长度)，上界指数级。

空间复杂度：O(路径长度)。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        path.add(0);
        dfs(0, graph, path, res);
        return res;
    }

    private void dfs(int node, int[][] graph, List<Integer> path, List<List<Integer>> res) {
        if (node == graph.length - 1) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int next : graph[node]) {
            path.add(next);
            dfs(next, graph, path, res);
            path.remove(path.size() - 1);
        }
    }
}

func allPathsSourceTarget(graph [][]int) [][]int {
	res := make([][]int, 0)
	path := []int{0}

	var dfs func(node int)
	dfs = func(node int) {
		if node == len(graph)-1 {
			tmp := make([]int, len(path))
			copy(tmp, path)
			res = append(res, tmp)
			return
		}

		for _, next := range graph[node] {
			path = append(path, next)
			dfs(next)
			path = path[:len(path)-1]
		}
	}

	dfs(0)
	return res
}

相似题目

题目	难度	考察点
399. 除法求值	中等	图遍历
841. 钥匙和房间	中等	图遍历
207. 课程表	中等	图遍历
200. 岛屿数量	中等	DFS
797. 所有可能的路径	中等	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/83983540