题目链接
题目分析
这个题,给了一个有向图的背景,然后要求我们把所有满足条件的路径都输出出来,看到返回值上的List<List
代码实现
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
boolean[] visited = new boolean[graph.length];
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
temp.add(0);
backTracking(graph,visited,0,res,temp);
return res;
}
public void backTracking(int[][] graph, boolean[] visited, int index, List<List<Integer>> res, List<Integer> temp){
if(visited[index]){
return;
}
if(graph[index].length == 0){
res.add(new ArrayList<>(temp));
return;
}
visited[index] = true;
for(int i = 0; i < graph[index].length; i++){
temp.add(graph[index][i]);
backTracking(graph,visited,graph[index][i],res,temp);
temp.remove(temp.size()-1);
}
//记得把visited状态还原
visited[index] = false;
}
}
我这里还是使用到了visited数组,我看到评论区中有说连这个数组都不用开的。说明自己还是熟练呀