关于算法:回溯算法最佳实践括号生成

读完本文，你能够去力扣拿下如下题目：

22. 括号生成

———–

括号问题能够简略分成两类，一类是前文写过的 括号的合法性判断，一类是非法括号的生成。对于括号合法性的判断，次要是借助「栈」这种数据结构，而对于括号的生成，个别都要利用回溯递归的思维。

对于回溯算法，咱们前文写过一篇 回溯算法套路框架详解 反应十分好，读本文前应该读过那篇文章，这样你就可能进一步理解回溯算法的框架应用办法了。

回到正题，括号生成算法是 LeetCode 第 22 题，要求如下：

请你写一个算法，输出是一个正整数 n，输入是 n 对儿括号的所有非法组合，函数签名如下：

vector<string> generateParenthesis(int n);

比如说，输出 n=3，输入为如下 5 个字符串：

“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”

无关括号问题，你只有记住以下性质，思路就很容易想进去：

1、一个「非法」括号组合的左括号数量肯定等于右括号数量，这个很好了解。

2、对于一个「非法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量。

如果不跟你说这个性质，可能不太容易发现，然而略微想一下，其实很容易了解，因为从左往右算的话，必定是左括号多嘛，到最初左右括号数量相等，阐明这个括号组合是非法的。

反之，比方这个括号组合 ))((，前几个子串都是右括号多于左括号，显然不是非法的括号组合。

上面就来手把手实际一下回溯算法框架。

回溯思路

明确了非法括号的性质，如何把这道题和回溯算法扯上关系呢？

算法输出一个整数 n，让你计算 n 对儿括号 能组成几种非法的括号组合，能够改写成如下问题：

当初有 2n 个地位，每个地位能够搁置字符 ( 或者 )，组成的所有括号组合中，有多少个是非法的？

这个命题和题目的意思齐全是一样的对吧，那么咱们先想想如何失去全副 2^(2n) 种组合，而后再依据咱们方才总结出的非法括号组合的性质筛选出非法的组合，不就完事儿了？

如何失去所有的组合呢？这就是规范的暴力穷举回溯框架啊，咱们前文 回溯算法套路框架详解 都总结过了：

result = []
def backtrack(门路, 抉择列表):
    if 满足完结条件:
        result.add(门路)
        return
    
    for 抉择 in 抉择列表:
        做抉择
        backtrack(门路, 抉择列表)
        撤销抉择

那么对于咱们的需要，如何打印所有括号组合呢？套一下框架就进去了，伪码如下：

void backtrack(int n, int i, string& track) {
    // i 代表以后的地位，共 2n 个地位
    // 穷举到最初一个地位了，失去一个长度为 2n 组合
    if (i == 2 * n) {print(track);
        return;
    }

    // 对于每个地位能够是左括号或者右括号两种抉择
    for choice in ['(', ')'] {track.push(choice); // 做抉择
        // 穷举下一个地位
        backtrack(n, i + 1, track);
        track.pop(choice); // 撤销抉择
    }
}

那么，当初可能打印所有括号组合了，如何从它们中筛选出非法的括号组合呢？​很简略，加几个条件进行「剪枝」就行了。

对于 2n 个地位，必然有 n 个左括号，n 个右括号，所以咱们不是简略的记录穷举地位 i，而是 用 left 记录还能够应用多少个左括号，用 right 记录还能够应用多少个右括号，这样就能够通过方才总结的非法括号法则进行筛选了：

vector<string> generateParenthesis(int n) {if (n == 0) return {};
    // 记录所有非法的括号组合
    vector<string> res;
    // 回溯过程中的门路
    string track;
    // 可用的左括号和右括号数量初始化为 n
    backtrack(n, n, track, res);
    return res;
}

// 可用的左括号数量为 left 个，可用的右括号数量为 rgiht 个
void backtrack(int left, int right, 
            string& track, vector<string>& res) {
    // 若左括号剩下的多，阐明不非法
    if (right < left) return;
    // 数量小于 0 必定是不非法的
    if (left < 0 || right < 0) return;
    // 当所有括号都恰好用完时，失去一个非法的括号组合
    if (left == 0 && right == 0) {res.push_back(track);
        return;
    }
    
    // 尝试放一个左括号
    track.push_back('('); // 抉择
    backtrack(left - 1, right, track, res);
    track.pop_back(); // 吊销抉择

    // 尝试放一个右括号
    track.push_back(')'); // 抉择
    backtrack(left, right - 1, track, res);
    track.pop_back();；// 吊销抉择}

这样，咱们的算法就实现了，算法的复杂度是多少呢？这个比拟难剖析，对于递归相干的算法，工夫复杂度这样计算（递归次数）*（递归函数自身的工夫复杂度）。

backtrack 就是咱们的递归函数，其中没有任何 for 循环代码，所以递归函数自身的工夫复杂度是 O(1)，但要害是这个函数的递归次数是多少？换句话说，给定一个 n，backtrack 函数递归被调用了多少次？

咱们后面怎么剖析动静布局算法的递归次数的？次要是看「状态」的个数对吧。其实回溯算法和动静布局的实质都是穷举，只不过动静布局存在「重叠子问题」能够优化，而回溯算法不存在而已。

所以说这里也能够用「状态」这个概念，对于 backtrack 函数，状态有三个，别离是 left, right, track，这三个变量的所有组合个数就是 backtrack 函数的状态个数（调用次数）。

left 和 right 的组合好办，他俩取值就是 0~n 嘛，组合起来也就 n^2 种而已；这个 track 的长度尽管取在 0~2n，但对于每一个长度，它还有指数级的括号组合，这个是不好算的。

说了这么多，就是想让大家晓得这个算法的复杂度是指数级，而且不好算，这里就不具体开展了，是 $\\frac{4^{n}}{\\sqrt{n}}$，有趣味的读者能够搜寻一下「卡特兰数」相干的常识理解一下这个复杂度是怎么算的。