1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
Map<Integer, Set<Integer>> nodeChildMap = new HashMap<>();
for (int i = 0; i < graph.length; i++) {
nodeChildMap.putIfAbsent(i, new HashSet<>());
Set<Integer> children = nodeChildMap.get(i);
for (int child : graph[i]) {
children.add(child);
}
}
List<List<Integer>> ans = new ArrayList<>();
backtrack(ans, new ArrayDeque<>(), new HashSet<>(), nodeChildMap, 0, graph.length);
return ans;
}
private void backtrack(List<List<Integer>> ans, Deque<Integer> currList, Set<Integer> visited,
Map<Integer, Set<Integer>> nodeChildMap, int currNode, int n) {
visited.add(currNode);
currList.offerLast(currNode);
if (currNode == n - 1) {
ans.add(new ArrayList<>(currList));
} else {
for (int child : nodeChildMap.get(currNode)) {
backtrack(ans, currList, visited, nodeChildMap, child, n);
}
}
currList.pollLast(currList.size() - 1);
visited.remove(currNode);
}
}
|
