问题描述
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例:
输入:n = 3
输出:[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/generate-parentheses
解答
''' 递归,dfs,回溯: 唯一独特的点,是用value表示括号是否匹配,value必不为负,当value=0的时候,匹配。 ''' class Solution: def generateParenthesis(self, n): result = [] def backtrack(self, arr, value): if len(arr) == 2*n: if value == 0: result.append(''.join(arr)) return if value >= 0: arr.append('(') value += 1 backtrack(self, arr, value) arr.pop() arr.append(')') value -= 2 backtrack(self, arr, value) arr.pop() else: return backtrack(self, [], 0) return result