心路历程:
一开始看到左右括号,第一想到了栈。后来发现题目要求遍历所有的可能组合,第一想法是暴力for循环,但是不知道用几个for循环,所以想到递归和回溯。
虽然叫‘括号组合’,但是实际上这是一个满足规则的全排列问题,这道题与前面的leetcode 17非常像,只是多了一步判断候选集合是否合法。
按照回溯问题的模板,维护候选集合和记录路径即可:维护一个栈,代表当前已经输出的括号,栈为空or栈里只有左括号时才行,进去一个右括号就消掉一个左括号。栈为空时,只能分配左括号。
代码写的有点啰嗦,不过思路很清楚,就没有在AC后进一步简化;里面有一些可以简化行数的点。
注意的点:
1、在任意一个遍历节点,需要保证当前左括号数量大于等于右括号,)(这种是不合法的。
2、注意这是一个满足候选集规则的全排列问题,在树的末端拷贝路径。
3、终止条件是遍历到空节点而不是叶子节点,即到2n而不是2n-1。
4、候选集的条件:1)还有某种类型的括号可以选;2)满足已选的左括号数量大于右括号。
class Solution:def generateParenthesis(self, n: int) -> List[str]:res = []path = []left = [['('] * n, [')'] * n]mystack = Mystack()def dfs(i):# 第i个节点,代表目前已经生成了i个括号,还有2n-i个需要遍历nonlocal nif i == 2 * n :res.append(''.join(path[:]))return# 按照规则选择括号candicates = []if mystack.len() == 0:if left[0] == []:candicates.append(')')else:candicates.append('(')else:# 一定剩有右括号if left[0] == []:candicates.append(')')else:candicates += ['(', ')']for each in candicates:if each == '(':path.append(each)left[0].pop()mystack.append(each, True)dfs(i+1)path.pop()left[0].append(each)mystack.pop()else:path.append(each)left[1].pop()mystack.append(each, False)dfs(i+1)path.pop()left[1].append(each)mystack.append('(', True)dfs(0)return resclass Mystack:def __init__(self): from collections import deque self.stack = deque([])def pop(self):return self.stack.pop()def append(self, ele, is_left):if is_left:self.stack.append(ele)else:assert self.stack != []self.stack.pop()def len(self):return len(self.stack)