深度优先算法-回溯算法-797. 所有可能的路径

Problem: 797. 所有可能的路径

Reference

代码随想录 (programmercarl.com)

思路

这是一道经典的深度优先算法，精华在于回溯，我们遍历当前节点的相邻节点，递归进行广度搜索，找到终点后，回溯到0，找不到终点也回溯到0。

这个回溯相当精妙，不好描述：

我知道怎么写，也知道是怎么一回事，就是无法用言语表达

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {

public:

    vector<int> path;

    vector<vector<int>> res;

    void back_tracing(vector<vector<int>>& graph, int x) {

        // 终止

        if (x == graph.size() - 1) {

            res.push_back(path);

            return;

        }

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

            path.push_back(graph[x][i]);

            back_tracing(graph, graph[x][i]);

            // 回溯

            path.pop_back();

        }

    }

  

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

        path.push_back(0);

        back_tracing(graph, 0);

        return res;

    }

};