[LeetCode] 22. 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:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
思路:

用DFS來掃出所有可能性, 關鍵在 第九行 遞迴式的 return.
如果左括號 大於 右括號的數量, 表明這不是一個合法的格式



class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        def dfs(l, r, path, res):
            print path
            if l > r : return
            if l == 0 and r == 0: res.append(path)
            if l > 0: dfs( l-1, r, path + '(' , res )
            if r > 0: dfs( l, r-1, path + ')' , res )
       
        path, res  = '', []
        if n == 0 : return []
        dfs( n, n, path, res )
        return res

留言