package question;

import java.util.LinkedList;
import java.util.List;

/*
 @author: Roderland
 @create: 2020年09月30日---22:54
*/
public class Question797 {
 public static void main(String[] args) {
 //[[1,2],[3],[3],[]]
 int[][] graph = new int[][]{{1, 2}, {3}, {3}, {}};
 new Question797().allPathsSourceTarget(graph);
 }

 List<List<Integer>> res = new LinkedList<>();
 int[][] graph;

 public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
 this.graph = graph;
 List<Integer> list = new LinkedList<>();
 list.add(0);
 dfs(0, list);
 return res;
 }

 public boolean dfs(int index, List<Integer> list) {
 if (index == graph.length - 1) return true;
 for (int i : graph[index]) {
 list.add(i);
 if (dfs(i, list)) res.add(new LinkedList<>(list));
 list.remove(list.size() - 1);
 }
 return false;
 }
}