方法：回溯

思路：

本題的方法是回溯，具體思路都在代碼注釋中已有體現。

遞歸三部曲：

1. 確定遞歸參數和返回值：private static void dfs(int node, int target)
2. 確定終止條件：如果遍歷到的node就是末尾，得到一條path，返回。if (node == target) res.add(new ArrayList(path));
3. 遞歸中的處理操作：一個for循環，遍歷當前node結點的鄰接表nodeList。遞歸完，記得回溯！記得回溯！記得回溯！

import java.util.*;public class Main {// 類變量，不用傳遞參數private static List<List<Integer>> graph = new ArrayList<>();private static List<List<Integer>> res = new ArrayList<>();private static List<Integer> path = new ArrayList<>();public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();// 創建n+1個，方便下標for (int i = 0; i <= n; i++) {graph.add(new ArrayList<>());}// 輸入邊for (int i = 0; i < m; i++) {int from = in.nextInt();int to = in.nextInt();graph.get(from).add(to);}// 從1開始path.add(1);dfs(1, n);// 輸出結果if (res.size() == 0) {System.out.println(-1);} else {print();}}private static void dfs(int node, int target) {// 如果該結點就是target，得到一條path，返回。if (node == target) {res.add(new ArrayList(path));return;}// 遍歷這個node的鄰接表nodeListList<Integer> nodeList = graph.get(node);for (int i : nodeList) {// path中加入元素path.add(i);// 下一層遞歸dfs(i, target);// 回溯：從path中移除元素path.remove(path.size() - 1);}}// 打印結果private static void print() {for (List<Integer> path : res) {// 先打第一個元素System.out.print(path.get(0));// 后面的元素都是空格+元素for (int i = 1; i < path.size(); i++) {System.out.print(" " + path.get(i));}// 打一個換行System.out.println("");}}
}

思路：

和上一題是同一道題，不過不用自己處理輸入和輸出。

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> allPathsSourceTarget(int[][] graph) {int target = graph.length - 1;path.add(0);dfs(graph, 0, target);return res;}private void dfs(int[][] graph, int node, int target) {if (node == target) {res.add(new ArrayList(path));return;}for (int i = 0; i < graph[node].length; i++) {path.add(graph[node][i]);dfs(graph, graph[node][i], target);path.remove(path.size() - 1);}}
}