July 25, 2022

797. All Paths From Source to Target

797. All Paths From Source to Target

DFS Backtracking

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        temp.add(0);
        dfsHelper(graph, res, temp, 0);
        return res;
    }
    
    private void dfsHelper(int[][] graph, List<List<Integer>> res, List<Integer> temp, int start) {
        if (start == graph.length - 1) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i : graph[start]) {
            temp.add(i);
            dfsHelper(graph, res, temp, i); 
            temp.remove(temp.size() - 1);
        }
    }
}
comments powered by Disqus