leetcode--22--括号生成

题目：数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

链接：https://leetcode-cn.com/problems/generate-parentheses

思路：
1、这道题可以使用回溯来做，使用left、right来代表左右括号的个数，如果left、right均为0，则说明括号都用完了，可以将当前结果curr放入总结果ret中。如果left大于0，说明还需要继续放左括号；如果右括号的个数小于做括号的个数，则继续放右括号

Python代码如下：

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        ret = []
        self.dfs(ret, n, n, '')

        return ret

    def dfs(self, ret, left, right, curr):
        if left ==0 and right==0:
            ret.append(curr)
        if left>0:
            self.dfs(ret,left-1,right,curr+'(')
        if right>left:
            self.dfs(ret,left,right-1,curr+')')