All Paths From Source to Target

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1, and return them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

Example 1:

Input: graph = {{1,2},{3},{3},{}}
Output: [[0,1,3],[0,2,3]]

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class AllPathsFromSourceToTarget {
    public static void main(String[] args) {
        int[][] graph = { { 1, 2 }, { 3 }, { 3 }, {} };
        List<List<Integer>> paths = allPathsSourceTarget(graph);
        System.out.println(Arrays.asList(paths));
    }

    static ArrayList<ArrayList<Integer>> arr;
    static Integer[] vis;

    static List<List<Integer>> res;

    private static void addEdge(int u, int v) {
        arr.get(u).add(v);
    }

    static List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        arr = new ArrayList<>();
        res = new ArrayList<List<Integer>>();
        int n = graph.length;
        vis = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr.add(new ArrayList<Integer>());
            vis[i] = 0;
        }
        for (int i = 0; i < n; i++) {
            int[] v = graph[i];
            for (int j = 0; j < v.length; j++)
                addEdge(i, v[j]);
        }
        List<Integer> path = new ArrayList<Integer>();
        path.add(0);
        dfs(0, n - 1, path);
        return res;
    }

    static void dfs(int node, int dest, List<Integer> path) {

        // if we reach at the destination
        if (node == dest) {
            List<Integer> l = new ArrayList<Integer>();
            l.addAll(path);
            res.add(l);
            return;
        }
        // mark as visited
        vis[node] = 1;

        // iterate for all adjacent nodes of the
        // current node
        for (Integer child : arr.get(node)) {
            // if not visited then call
            // for it
            if (vis[child].equals(0)) {
                // add into the path
                path.add(child);
                dfs(child, dest, path);
                path.remove(child);
            }
        }
        // backtrack
        vis[node] = 0;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;


vector<int> arr[100001];
int vis[100001];
int n;
vector<vector<int> > res;


void dfs(int node,vector<int> path)
{

    //mark as visited 
    vis[node]=1;

    //add into the path
    path.push_back(node);

    //if we reach at the destination
     if(node==n-1)
        res.push_back(path);

    //else 
    else
        {

            //iterate for all adjacent nodes of the
            //current node
            for(int child:arr[node])
            {

                //if not visited then call
                //for it
                if(vis[child]==0)
                      dfs(child,path);
            }
        }
     //backtrack
         vis[node]=0;
}

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph)
{
    n=graph.size();
        for(int i=0;i<graph.size();i++)
        {
            vis[i]=0;
            arr[i].clear();
        }
        for(int i=0;i<graph.size();i++)
        {
            vector<int> v=graph[i];
            for(int j=0;j<v.size();j++)
                arr[i].push_back(v[j]);
        }
        res.clear();
        vector<int> path;
        dfs(0,path);
       return res; 
}

int main()
{
    vector<vector<int>> graph ={{1,2},{3},{3},{}};
    vector<vector<int>> paths=allPathsSourceTarget(graph);
    cout<<"[";
    for(int i=0;i<paths.size();i++)
      {
          cout<<"[";
          for(int j=0;j<paths[i].size();j++)
           {
               cout<<paths[i][j];
               if(j!=paths[i].size()-1)
                 cout<<",";
           }
         cout<<"]";
          if(i!=paths.size()-1)
            cout<<",";
      }
    cout<<"]";

    return 0;
}