2

算法系列：回溯

 2 years ago
source link: https://muyuuuu.github.io/2022/05/28/backtrack/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

回溯算法是一种暴力枚举的算法。但是，枚举是一个技术活，枚举过程如何保证不重复、剪纸、不遗漏和优先处理可能的结果，这并不简单。

回溯应该是算法系列中除动态规划外最难的一个，需要很好的明确回溯入口，退出条件，两者保证回溯的不遗漏。而下一步如何回溯，以及如何退出当前状态要保证回溯的不重复。也许有些抽象，我们来看具体例子。

什么是回溯

如果简单的说回溯，那么如下函数就可以解释清楚：

for (auto i : arr) {
    backtrack(i);
}
void backtrack(int i) {
    if (i > n)
        退出条件
    // 回溯入口
    for (auto j : arr[i]) {
        vector.push_back(j);
        // 下一步而回溯
        backtrack(j);
        // 退出当前的状态，往回走
        // 因此叫做回溯
        vector.pop_back()
    }
}

797. 所有可能的路径

给你一个有 n 个节点的 有向无环图 DAG，请你找出所有从节点 0 到节点 n-1 的路径并输出，不要求按特定顺序。graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

如果说从 0 开始，而 0 又指向 1 和 2，那么只能按照这样的顺序找下去，因为题目并没有说要求最短路径。如果遍历的是 0，1，3，那么在找完这条路径后，需要回退，找到 0，1，2 这条路径。也就是，这算是一道回溯类题目。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmp;
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        tmp.push_back(0);
        int n = graph.size();
        // 回溯入口
        dfs(0, n, graph);
        return res;
    }

void dfs(int idx, int n, vector<vector<int>>& graph) {
        // 退出条件
        if (idx >= n - 1) {
            res.push_back(tmp);
            return;
        } else {
            // 回溯入口
            for (auto i : graph[idx]) {
                tmp.push_back(i);
                dfs(i, n, graph);
                // 回溯
                tmp.pop_back();
            }
        }
    }
};

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK