题目描述

给一个有 N 个结点的有向无环图，找到所有从 0 到 N-1 的路径并输出（不要求按顺序）。

这个图以如下方式给出：结点编号为 0, 1, ..., graph.length - 1。graph[i] 是一个数组，包含了所有 (i, j) 边存在的结点 j。

样例

输入: [[1,2], [3], [3], []] 
输出: [[0,1,3],[0,2,3]] 
解释: 图是这样的:
0--->1
|    |
v    v
2--->3
这有两条路: 0 -> 1 -> 3 和 0 -> 2 -> 3。

提示

• 结点的数量会在范围 [2, 15] 内。
• 你可以把路径以任意顺序输出，但在路径内的结点的顺序必须保证。

算法

(深度优先遍历 / DFS) $O(n \cdot 2^n)$

1. 从 0 号结点开始沿着路径进行深度优先遍历。
2. 在递归中，假设当前结点为 u，则枚举 u 的所有相邻的结点 v，将 v 加入到当前路径中，然后递归到下一个结点 v。
3. 如果当前结点为 N - 1 则将当前路径加入到答案数组中，进行回溯。

时间复杂度

• 每个点最多有两种选择，存放答案是需要 $O(n)$ 的拷贝时间，故时间复杂度为 $O(n \cdot 2^n)$。

空间复杂度

• 由于是有向无环图，递归最深也就 $n$ 层，需要 $O(n)$ 的空间存放系统栈。
• 当前路径记录数组需要 $O(n)$ 的空间。
• 答案最多有 $2^n$ 个，故答案数组需要 $O(n \cdot 2^n)$ 的空间，故时间复杂度为 $O(n \cdot 2^n)$。

C++ 代码

class Solution {
public:
    void dfs(const vector<vector<int>>& graph,
             vector<vector<int>> &ans,
             vector<int> &ch, int u) {

        if (u == graph.size() - 1) {
            ans.push_back(ch);
            return;
        }

        for (auto &v : graph[u]) {
            ch.push_back(v);
            dfs(graph, ans, ch, v);
            ch.pop_back();
        }
    }

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