All Paths From Source to Target

Problem Link:

https://leetcode.com/problems/all-paths-from-source-to-target/description/

Hint:

Solution:

// TIME COMPLEXITY : O(N+E);
//SPACE COMPLEXITY : O(N) + Auxiliary Space O(N)


class Solution {
public:
    void dfs(vector<vector<int>> &adj, int src, int dest, 
    vector<int> &temp, vector<vector<int>> &output){

        if(src==dest){
            output.push_back(temp);
            return;
        }

        for(auto it: adj[src]){
            if(it!=src){
                temp.push_back(it);
                dfs(adj,it,dest,temp,output);
                temp.pop_back();
            }
        }
        return;

    }
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> output;
        vector<int> temp;

        int n = graph.size();

        temp.push_back(0);
        dfs(graph,0,n-1,temp,output);

        return output;
    }
};