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]).

&nbsp;
Example 1:

Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -&gt; 1 -&gt; 3 and 0 -&gt; 2 -&gt; 3.


Example 2:

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


&nbsp;
Constraints:


	n == graph.length
	2 &lt;= n &lt;= 15
	0 &lt;= graph[i][j] &lt; n
	graph[i][j] != i (i.e., there will be no self-loops).
	All the elements of graph[i] are unique.
	The input graph is guaranteed to be a DAG.


class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        res = []
        self.explore(graph, graph[0], [0], res)
        return res
    
    def explore(self, graph, candidates, step, res):
        if step[-1] == len(graph)-1:
            res.append(list(step))
        else:
            for i in range(len(candidates)):
                step.append(candidates[i])
                self.explore(graph, graph[candidates[i]], step, res)
                step.pop()
Approach : Using dfs+ backtracking we can solve it	
	
	class Solution {
		public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
			List<List<Integer>> ans=new ArrayList<>();
			List<Integer> temp=new ArrayList<>();
			 boolean []visit=new boolean [graph.length];
			helper(graph,0,graph.length-1,ans,temp,visit);

			return ans;
		}
		public void helper(int[][] graph, int src,int dest,List<List<Integer>> ans,List<Integer> temp,boolean[]vis)
		{

			vis[src]=true;
			temp.add(src);
			if(src==dest)
			{
				List<Integer> b =new ArrayList<>();
				for(int h:temp){
					b.add(h);
				}
				ans.add(b);
			}

			for(int i:graph[src])
			{
				if(vis[i]!=true)
				{
					helper(graph,i,dest,ans,temp,vis);
				}

			}

			vis[src]=false;
			temp.remove(temp.size()-1);
		}
	}
class Solution {
public:
    // setting a few class variables, so that we do not have to pass them down all the time in the recursive dfs calls
    int target;
    vector<vector<int>> res;
    vector<int> tmp;
    void dfs(vector<vector<int>>& graph, int currNode = 0) {
	    // updating tmp
        tmp.push_back(currNode);
		// and either updating res with it if target is met
        if (currNode == target) res.push_back(tmp);
		// or callling dfs again recursively
        else for (int node: graph[currNode]) {
            dfs(graph, node);
        }
        // backtracking with tmp
		tmp.pop_back();
    }
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        target = graph.size() - 1;
        dfs(graph);
        return res;
    }
};
/**
 * @param {number[][]} graph
 * @return {number[][]}
 */
const allPathsSourceTarget = function(graph) {
    const n = graph.length;
    const result = [];
    const dfs = (node, path) => {
        if (node === n-1) {
            result.push([...path, node]); // Add the current path to the result if we have reached the target node
            return;
        }
        for (const neighbor of graph[node]) {
            dfs(neighbor, [...path, node]); // Recursively explore all neighbors of the current node
        }
    };
    dfs(0, []); // Start the DFS from the source node
    return result;
};
All Paths From Source to Target