797 - All Paths From Source To Target

#medium

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] ]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 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] ]

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;

    // x為當前節點index
    void dfs( vector<vector<int>> graph, int x ) {
        if ( x == graph.size() - 1 ) {
            result.push_back( path );
            return;
        }

        // 單個node到其他node的方法
        for ( int i = 0; i < graph[x].size(); i++ ) {
            path.push_back( graph[x][i] );
            dfs( graph, graph[x][i] );
            path.pop_back();
        }        

    }

    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        path.push_back( 0 );
        dfs( graph, 0 );
        return result;
    }

DFS

void dfs(參數) {
    if (終止條件) {
        存放結果;
        return;
    }

    for (選擇：本節點所連接的其他節點) {
        處理節點;
        dfs(圖，選擇的節點); // 遞歸
        回溯，撤銷處理結果
    }
}