回溯练习题

面试题 08.09. 括号(Medium)

打印n对括号的所有合法的组合。

样例

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

代码

def backtracking(l, r, ans, tmp):
    if l == 0 and r == 0: # 找到
        ans.append(tmp)
        return 

    if l > r : # 数目不匹配
        return 

    if l > 0:
        backtracking(l - 1, r, ans, tmp + '(')
        
    if r > 0:
        backtracking(l, r - 1, ans, tmp + ')')
        
    
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = [] 
        backtracking(n, n, ans, '')
        return ans 

func backtracking(l int, r int, tmp string) {
    if l == 0 && r == 0 { // 找到答案
        ans = append(ans, tmp)
        return 
    }

    if l > r { // 括号没有一一匹配
        return
    }

    if l > 0 {
        backtracking(l - 1, r, tmp + "(")
    }

    if r > 0 {
        backtracking(l, r - 1, tmp + ")")
    }

}

var ans []string
func generateParenthesis(n int) []string {
    ans = []string{}
    backtracking(n, n, "")
    return ans 
}