Description:

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: [ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]

解法：

看到这道题首先想到了DFS，递归可以解决这个问题。

对于递归类问题，解题思路大体是：在当前局面下，你有若干种选择。那么尝试每一种选择。如果已经发现某种选择肯定不行（因为违反了某些限定条件），就返回；如果某种选择试到最后发现是正确解，就将其加入解集。简而言之，只要明确三点就行：选择 (Options)，限制 (Restraints)，结束条件 (Termination)。结束条件与限制均返回，两者的区别在于结束条件是合法搜索完了返回，而限制是遇上了非法情况返回的。

对于这道题，在任何时刻，你都有两种选择：

加左括号。
加右括号。

这部分构成了递归体

结束条件也很明确：

左右括号都已经用完了

这部分构成了合法完成搜索的递归出口

而限制则考虑搜索过程中的非法情况，即出现了这种情况不再进行递归搜索而返回：

对于该题，从左括号与右括号的数量入手，两者数目相同，显然合法；如果剩余的右括号数量大于左括号数量，说明之前存在没有与右括号匹配的左括号，这种情况是合法有效的；若出现左括号数目大于右括号的情况，则对于之后添加的左括号，一定会存在没有右括号与之匹配的情况，这种情况非法，不用再继续进行搜索了。简而言之：

如果左括号剩余量大于右括号，会出现非法情况，返回

代码如下：

class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        res = [];
        Solution.dfs(n,n,"",res);
        return res;
        
    def dfs(left,right,nowstr,res):
        if(left>right):
            return;
        if(left == 0 and right == 0):
            res.append(nowstr);
            return;
        if(left > 0):
            Solution.dfs(left - 1, right ,nowstr + '(',res);
        if(right > 0):
            Solution.dfs(left,right - 1,nowstr + ')', res);