動機

複習backtrack，比起以前的commit，發現現在code越寫越短了

Problem

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

 

Example 1:

Input: n = 3Output: [((())),(()()),(())(),()(()),()()()]

Example 2:

Input: n = 1Output: [()]

 

Constraints:

  • 1 <= n <= 8

Sol

每次就是加左或是右括號，左隨時都可以加，但是右必須在有加過左時才可以加

def dfs(left,right,s):
    if left == 0:
        return [s + ')'*right]
    else:
        ret = dfs(left-1,right,s+'(')
        if left < right:
            ret += dfs(left,right-1,s+')')
        return ret
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        return dfs(n,n,"")