题目

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

分析

方法一：暴力法（递归）

思路

我们可以生成所有 $2^{2n}$ 个 '(' 和')' 字符构成的序列。然后，我们将检查每一个是否有效。

算法

为了生成所有序列，我们使用递归。长度为 n 的序列就是'('加上所有长度为 n-1 的序列，以及')'加上所有长度为 n-1 的序列。

为了检查序列是否为有效的，我们会跟踪平衡，也就是左括号的数量减去右括号的数量的净值。如果这个值始终小于零或者不以零结束，该序列就是无效的，否则它是有效的。

方法一改进版：递归法

这道题给定一个数字n，让生成共有n个括号的所有正确的形式，对于这种列出所有结果的题首先还是考虑用递归Recursion来解，由于字符串只有左括号和右括号两种字符，而且最终结果必定是左括号3个，右括号3个，所以我们定义两个变量left和right分别表示剩余左右括号的个数，如果在某次递归时，左括号的个数大于右括号的个数，说明此时生成的字符串中右括号的个数大于左括号的个数，即会出现’)(‘这样的非法串，所以这种情况直接返回，不继续处理。如果left和right都为0，则说明此时生成的字符串已有3个左括号和3个右括号，且字符串合法，则存入结果中后返回。如果以上两种情况都不满足，若此时left大于0，则调用递归函数，注意参数的更新，若right大于0，则调用递归函数，同样要更新参数。

这种递归的方法和第一种暴力法很像，核心思想都是先产生字符串，一旦不符合规则立刻舍弃，但是这样会增加时间复杂度，我们可以直接产生符合要求的字符串，然后添加到vector中，这就需要我们有一个比较严谨的逻辑条件。请看方法二

方法二：回溯法（重点掌握）

思路和算法
类似于此题，要求解出所有的排列组合，我们优先考虑递归法或者回溯法
只有在我们知道序列仍然保持有效时才添加'('or')'，而不是像方法一那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，

如果我们还剩一个位置，我们可以开始放一个左括号。 如果它不超过左括号的数量，我们可以放一个右括号。

方法三：闭合法

思路

为了枚举某些内容，我们通常希望将其表示为更容易计算的不相交子集的总和。

考虑有效括号序列 S 的闭包数：至少存在index> = 0，使得S[0], S[1], ..., S[2*index+1]是有效的。 显然，每个括号序列都有一个唯一的闭包号。 我们可以尝试单独列举它们。

算法

对于每个闭合数c，我们知道起始和结束括号必定位于索引0和2*c + 1。然后两者间的2*c个元素一定是有效序列，其余元素一定是有效序列。

代码

法一：暴力法（java）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }

    public void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (valid(current))
                result.add(new String(current));
        } else {
            current[pos] = '(';
            generateAll(current, pos+1, result);
            current[pos] = ')';
            generateAll(current, pos+1, result);
        }
    }

    public boolean valid(char[] current) {
        int balance = 0;
        for (char c: current) {
            if (c == '(') balance++;
            else balance--;
            if (balance < 0) return false;
        }
        return (balance == 0);
    }
}

def generateParenthesis(self, N):
    if N == 0: return ['']
    ans = []
    for c in xrange(N):
        for left in self.generateParenthesis(c):
            for right in self.generateParenthesis(N-1-c):
                ans.append('({}){}'.format(left, right))
    return ans

法一改进版：递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        generateParenthesisDFS(n, n, "", res);
        return res;
    }
    void generateParenthesisDFS(int left, int right, string out, vector<string> &res) {
        if (left > right) return;
        if (left == 0 && right == 0) res.push_back(out);
        else {
            if (left > 0) generateParenthesisDFS(left - 1, right, out + '(', res);
            if (right > 0) generateParenthesisDFS(left, right - 1, out + ')', res);
        }
    }
};

法二：回溯法（java）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        backtrack(ans, "", 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, String cur, int open, int close, int max){
        if (cur.length() == max * 2) {
            ans.add(cur);
            return;
        }

        if (open < max)
            backtrack(ans, cur+"(", open+1, close, max);
        if (close < open)
            backtrack(ans, cur+")", open, close+1, max);
    }
}

法三：闭合法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        if (n == 0) {
            ans.add("");
        } else {
            for (int c = 0; c < n; ++c)
                for (String left: generateParenthesis(c))
                    for (String right: generateParenthesis(n-1-c))
                        ans.add("(" + left + ")" + right);
        }
        return ans;
    }
}

个人总结

递归与回溯的区别

递归：为了描述问题的某一状态，必须用到该状态的上一状态，而描述上一状态，又必须用到上一状态的上一状态……这种用自已来定义自己的方法，称为递归定义。形式如 f(n) = n*f(n-1), if n=0,f(n)=1.

解答树角度：在dfs遍历一棵解答树

优点：结构简洁

缺点：效率低，可能栈溢出
递归一般结构：

1
2
3
4
5
6
7
8
9
10
11
void f()  
{  
     if(符合边界条件)  
    {  
       ///////  
        return;  
    }  
      
     //某种形式的调用  
     f();  
}

回溯：从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到” 尽头 “的时候, 再倒回出发点, 从另一个可能出发, 继续搜索. 这种不断” 回溯 “寻找解的方法, 称作” 回溯法 “。递归的一种，或者说是通过递归这种代码结构来实现回溯这个目的。回溯法可以被认为是一个有过剪枝的DFS过程。

解答树角度：带回溯的dfs遍历一棵解答树

回溯的一般结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(int 当前状态)  
    {  
          if(当前状态为边界状态)  
          {  
            记录或输出  
            return;  
          }  
          for(i=0;i<n;i++)       //横向遍历解答树所有子节点  
         {  
               //扩展出一个子状态。  
               修改了全局变量  
               if(子状态满足约束条件)  
                {  
                  dfs(子状态)  
               }  
                恢复全局变量//回溯部分  
            }  
    }

DFS与BFS

BFS：Breadth-First-Search，宽度优先搜索；
BFS是从root开始扩展，每一层都是精密的搜索完整了才下一个

DFS：Depth-first search，深度优先搜索。
DFS主要的特性是深度优先，总是不停的往下找，走到没路才罢休。

关于此题

这道题就是灵活运用递归和回溯，可以看出来我们有两次判断，一个判断就是如果括号有n组，那么左括号一定不能大于n，而且，当左括号数量大于右括号时，我们开始有了分类，可以继续插入左括号（如果满足条件一的话），也可以插入右括号。核心的思想还是要想到递归。关于列出所有排列组合的情况，优先考虑递归回溯。