题解 | #括号生成#

括号生成

http://www.nowcoder.com/practice/c9addb265cdf4cdd92c092c655d164ca

NC26 括号生成

题意分析：

给定数字n，枚举出n对括号可组成的合法组合。

题解一（暴力枚举）：

n对括号，一共2n个字符。用这2n个字符生成 $2^{2n}$ 个序列，并且检查每一个序列是否时合法的括号序列。生成序列我们可以使用递归。判断生成的可以使括号序列用一种平衡的思想。假设一个括号序列有值。左括号（对值贡献为+1，右括号对值贡献-1。一个合法的括号序列每一部分都是平衡的，为0。如果在遍历判断括号序列是否合法的时候，发现此时的值小于0，说明右括号数目比左括号数目多如：())(。遍历到第三个位置，括号序列的值为-1。这时就可以认为该括号序列是不合法的。在遍历结束的时候，如果括号序列值不为0，我们也可以认为其不是合法的。

以n=3 为例子，下图是括号的回溯过程
图片说明

bool valid(const string &str) {
    //判断给定字符串是否是一个合法的括号序列
    int ret = 0;
    for (char c : str) {
        if (c == '(') {
            //左括号ret+1
            ret++;
        } else {
            //右括号ret--；
            ret--;
        }
        if (ret < 0) {
            //())这种情况会导致ret<0,非法括号序列直接返回false
            return false;
        }
    }
    //如果括号序列是合法的，那么最后ret一定等于0
    return ret == 0;
}

void generate_all(string &thesis, int n, vector<string> &result) {
    if (thesis.size() == n) {
        if (valid(thesis)) {
            //生成括号序列并判断是否合法，合法加入到最后结果中。
            result.push_back(thesis);
        }
        return;
    }
    thesis += '(';
    generate_all(thesis, n, result);
    thesis.pop_back();
    thesis += ')';
    generate_all(thesis, n, result);
    thesis.pop_back();
}

vector<string> generateParenthesis(int n) {
    vector<string> result;
    string s;
    generate_all(s, n * 2, result);
    return result;
}

时间复杂度： $O(n2^{2n})$ 。我们生成了 $2^{2n}$ 个括号序列，并且对每个序列进行了一次 $O(n)$ 复杂度的判断。

空间复杂度：O(n)。递归深度最多为2n。

题解二：（暴力+剪枝）

在题解一中，我们对2n个由()组成的字符序列进行了枚举，然后再进行验证合法性。其实我们可以减少枚举的数量。我们只有n个左括号，和n个右括号使用，来组成括号序列。生成括号序列的步骤如下

新建一个空字符序列s
从左括号和右括号中选择一种加入到s中。s的左括号数量或右括号数量加一
当s的长度等于2n，或者没有左括号或右括号可以使用，返回s

根据上面对字符串的合法性判断的算法，我们可以得出如下结论：s中已经加入的左括号数量一定大于等于右括号数量。我们设置如下函数backtrack(string s,int l,int r,int n,vector<stirng>&ret)，s初始化为空字符串，l为s中左括号数目，r为s中右括号数目，n为括号对数目，ret存放最后结果。

我们代码实现如下：

void backtrack(string s,int l,int r,int n,vector<string>&ret){
    //当左括号或者右括号数目大于n，或者右括号数目大于左括号数目，不能加入到结果中，直接返回
    if(l>n||r>n||r>l) return;
    //当生成的括号序列长度为2n时候，合法
    if(s.size()==2*n){
        ret.push_back(s);
        return;
    }
    //s后追加一个左括号，左括号数目加一
    backtrack(s+'(',l+1,r,n,ret);
    //s后追加一个右括号，右括号数目加一
    backtrack(s+')',l,r+1,n,ret);
    return;
}
vector<string> generateParenthesis(int n) {
    vector<string>ret;
    backtrack("",0,0,n,ret);
    return ret;
}

时间复杂度：和能够生成有效括号序列个数有关。

空间复杂度： $O(n)$ ，在我们递归的时候，最多需要递归2n层，因此为 $O(n)$ 。