数据结构与算法===回溯法

文章目录

原理
使用场景
- 括号生成
- 代码
小结

原理

回溯法是采用试错的思想，它尝试分步骤的去解决一个问题。在分步骤解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能得分步解答再次尝试寻找问题的答案。

百度百科是这么解释的。

使用场景

现在聊聊使用场景的问题，之前的文章深度优先采用的就是回溯的思想。就是在当前层级一个一个试完，然后再去下一个层级遍历。可以去看看这篇文章。下边再看一个案例吧。

括号生成

在这里插入图片描述

代码

这个是Java的,如下：

class Solution {
    ArrayList<String> result = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        _generate(0, 0, n, "");
        return result;
    }

     private void _generate(int left, int right, int n, String s) {
        if (left == right && left == n) {
            result.add(s);
            return;
        }

        if(left < n) {
            _generate(left + 1, right, n, s + "(");
        }

        if (left > right) {
            _generate(left, right + 1, n, s + ")");
        }
    }
}

下边看看c++的，如下：

class Solution {
    shared_ptr<vector<string>> cache[100] = {nullptr};
public:
    shared_ptr<vector<string>> generate(int n) {
        if (cache[n] != nullptr)
            return cache[n];
        if (n == 0) {
            cache[0] = shared_ptr<vector<string>>(new vector<string>{""});
        } else {
            auto result = shared_ptr<vector<string>>(new vector<string>);
            for (int i = 0; i != n; ++i) {
                auto lefts = generate(i);
                auto rights = generate(n - i - 1);
                for (const string& left : *lefts)
                    for (const string& right : *rights)
                        result -> push_back("(" + left + ")" + right);
            }
            cache[n] = result;
        }
        return cache[n];
    }
    vector<string> generateParenthesis(int n) {
        return *generate(n);
    }
};