All Paths From Source to Target

1package pkg5leetcode.official75;2 3/*4 * All Paths From Source to Target | LC 7975 * APPROACH: Backtracking DFS build path to target.6 * COMPLEXITY: Time O(2^n), Space O(n)7 */8import java.util.*;9 10public class official75_LC797AllPathsFromSourceToTarget {11    static List<List<Integer>> allPathsSourceTarget(int[][] graph) {12        List<List<Integer>> res = new ArrayList<>();13        List<Integer> path = new ArrayList<>();14        path.add(0);15        dfs(0, graph, path, res);16        return res;17    }18 19    static void dfs(int node, int[][] graph, List<Integer> path, List<List<Integer>> res) {20        if (node == graph.length - 1) {21            res.add(new ArrayList<>(path));22            return;23        }24        for (int nxt : graph[node]) {25            path.add(nxt);26            dfs(nxt, graph, path, res);27            path.remove(path.size() - 1);28        }29    }30 31    public static void main(String[] args) {32        List<List<Integer>> r = allPathsSourceTarget(new int[][]{{1,2},{3},{3},{}});33        check(r.size() == 2, "case1");34        check(allPathsSourceTarget(new int[][]{{1,2},{3},{3},{}}).size() == 2, "case2");35        System.out.println("all tests passed");36    }37 38    static void check(boolean cond, String name) {39        if (!cond) throw new AssertionError("FAILED: " + name);40        System.out.println("  PASS " + name);41    }42}