題目

https://leetcode.com/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. 所有可能的路径（回溯法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。