Generate Parentheses

发表于 | 分类于

[Leetcode] Generate Parentheses

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:

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
	def generateParenthesis(self, n):
	    """
	    :type n: int
	    :rtype: List[str]
	    """
	    res = []
	    res = helper(n,n,'',res)
	    return res
	
	
	def helper(left,right,out,res):
	    if left < 0 or right < 0 or left > right:
	        return res
	    if left == 0 and right == 0:
	        res.append(out)
	        return res
	    if left > 0:
	        helper(left -1, right, out + '(', res)
	    if right > 0:
	        helper(left, right -1, out + ')', res)
	    return res

别人用循环完成的代码：

1
2
3
4
5
6
7
8
9
class Solution(object):
    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