Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is: 

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

思路

求取组合数，或是要求取给定条件的所有情况，可以利用回溯+递归的方法来解决。

在往下寻找每一种情况并回溯的时候，会由于条件所限，去除许多不必要的分支。所以算法实际的复杂度会比纯暴力搜索的方法降低许多。

  • 解释一下递归函数trial(self, cur, tmp, tmpsum, trues, falses, n)当中各个变量的含义：

cur: 当前需要加入临时数组的变量【 “(“ 或 “)” 】【True 或 False】

tmp: 一个临时数组，存储递归到当前深度True/False的所有值。

tmpsum: 递归当前深度数组的和 (True + True = 2， False + False = 0)【其实可以把这个变量删去，只用统计Trues和falses的值就好】

trues / falses: 左括号和右括号的个数

  • 关键判断语句：

if (tmpsum * 2 < trues + falses):

或是

if (trues < falses)

如果访问到当前元素，左括号的数目比右括号要少，即可判定为非法。

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
import copy
class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        # True for '('
        # False for ')'
        self.res = []
        tmpsum = 0
        self.trial(True, [], tmpsum, 1, 0, n)
        return self.res
        
    def trial(self, cur, tmp, tmpsum, trues, falses, n):
        tmp.append(cur)
        tmpsum += cur
        if (tmpsum * 2 < trues + falses):
            tmp = []
            return
        elif (trues == n and falses == n):
            ans = []
            for i in tmp:
                if (i):
                    ans.append("(")
                else:
                    ans.append(")")
            self.res.append("".join(ans))
        else:
            if (trues < n):
                cpy = copy.copy(tmp)
                self.trial(True, cpy, tmpsum, trues+1, falses, n)
            if (falses < n):
                cpy = copy.copy(tmp)
                self.trial(False, cpy, tmpsum, trues, falses+1, n)