## Monday, April 23, 2018

### LeetCode 797 - All Paths From Source to Target

https://leetcode.com/problems/all-paths-from-source-to-target/description/
Given a directed, acyclic graph of N nodes.  Find all possible paths from node 0 to node N-1, and return them in any order.
The graph is given as follows:  the nodes are 0, 1, ..., graph.length - 1.  graph[i] is a list of all nodes j for which the edge (i, j) exists.
Example:
Input: [[1,2], [3], [3], []]
Output: [[0,1,3],[0,2,3]]
Explanation: The graph looks like this:
0--->1
|    |
v    v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Note:
• The number of nodes in the graph will be in the range [2, 15].
• You can print different paths in any order, but you should keep the order of nodes inside one path.
Since the graph is a directed, acyclic graph, any path from A to B is going to be composed of A plus a path from any neighbor of A to B. We can use a recursion to return the answer.
Algorithm
Let N be the number of nodes in the graph. If we are at node N-1, the answer is just the path {N-1}. Otherwise, if we are at node node, the answer is {node} + {path from nei to N-1} for each neighbor nei of node. This is a natural setting to use a recursion to form the answer.
• Time Complexity: $O(2^N N^2)$. We can have exponentially many paths, and for each such path, our prepending operation path.add(0, node) will be $O(N^2)$.
• Space Complexity: $O(2^N N)$, the size of the output dominating the final space complexity.
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
return solve(graph, 0);
}

public List<List<Integer>> solve(int[][] graph, int node) {
int N = graph.length;
List<List<Integer>> ans = new ArrayList();
if (node == N - 1) {
List<Integer> path = new ArrayList();
return ans;
}

for (int nei: graph[node]) {
for (List<Integer> path: solve(graph, nei)) {
}
}
return ans;
}

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<vector<int>> ans;
vector<int> path{0};
dfs(graph, path, ans);
return ans;
}
private:
void dfs(const vector<vector<int>>& graph,
vector<int>& path, vector<vector<int>>& ans) {
if (path.back() == graph.size() - 1) {
ans.push_back(path);
return;
}

for (int next : graph[path.back()]) {
path.push_back(next);
dfs(graph, path, ans);
path.pop_back();
}
}

// TLE, but after remove useCache, it passed
// need remove duplicate paths
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
if (graph == null)
return new ArrayList<>();

return allPaths.stream().map(el -> new ArrayList<>(el)).collect(Collectors.toList());
}

private void allPathsSourceTarget(int[][] graph, int node, LinkedHashSet<Integer> path,
if (node == graph.length - 1) {
path.remove(node); // don't miss this
return;
}

// cache
if (useCache(allPaths, node, path)) {
path.remove(node);
return;
}

for (int i = 0; i < graph[node].length; i++) {
allPathsSourceTarget(graph, graph[node][i], path, allPaths);
}

path.remove(node);
}

boolean nodeVisited = false;

for (LinkedHashSet<Integer> cache : allPaths) {
if (cache.contains(node)) {
nodeVisited = true;
boolean foundIt = false;
for (Integer tmp : cache) {
if (foundIt) {
} else if (Objects.equals(tmp, node)) {
foundIt = true;
} // else continue
}

// ConcurrentModificationException

}
}

return nodeVisited;

}