hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

All Paths From Source to Target


  • Approach:

    1. As it said the source will be 0 and the destination will be n-1, we will just run a DFS starting from source 0.

    2. While moving through the adjacent nodes of 0, we will put them in the nodes vector. The nodes will temporarily hold the traversed node on a path.

    3. Later when we reach n-1, we will add the node into another vector say, nodes.

    4. While coming back to n-1's immediate parent we will remove n-1 from the nodes. We will do the same for this parent's immediate parent.

    5. We will check for the rest of the children of those nodes.

    6. We will keep doing this until we are done traversing all the nodes.

    7. Later we will return ansList.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(N) + Stack


Code [C++]

class Solution {

public:


void dfs(int src, int dest, vector<vector<int>> & graph, vector<vector<int>> & ansList, vector<int> & nodes){

if(src == dest){

ansList.push_back(nodes);

return;

}


for(int i=0; i<graph[src].size(); i++){

int child = graph[src][i];

nodes.push_back(child);

dfs(child, dest, graph, ansList, nodes);

nodes.pop_back();

}

}


vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {

vector<vector<int>>ansList;

vector<int>nodes;

int n = graph.size();

nodes.push_back(0);

dfs(0, n-1, graph, ansList, nodes);

return ansList;

}

};