题目
/problems/all-paths-from-source-to-target/
题解
回溯,中规中矩,直接上代码。
class Solution {int N;public List<List<Integer>> allPathsSourceTarget(int[][] graph) {N = graph.length;boolean[][] g = new boolean[N][N];for (int i = 0; i < N; i++) {for (int j : graph[i]) {g[i][j] = true;}}return process(g, 0, new HashSet<>());}// 从 i 出发,到达 n-1 的全部路径public List<List<Integer>> process(boolean[][] g, int i, Set<Integer> seen) {List<List<Integer>> result = new ArrayList<>();if (i == N - 1) {// 已到终点result.add(new ArrayList<>());result.get(0).add(N - 1);return result;} else {// 未到终点for (int j = 0; j < N; j++) {// i -> j -> N-1if (g[i][j] && !seen.contains(j)) {// backtracingseen.add(j);for (List<Integer> path : process(g, j, seen)) {List<Integer> list = new ArrayList<>();list.add(i);list.addAll(path);result.add(list);}seen.remove(j);}}}return result;}}
如果觉得《leetcode 797. All Paths From Source to Target | 797. 所有可能的路径(回溯法)》对你有帮助,请点赞、收藏,并留下你的观点哦!