Leetcode 22. 括号生成

心路历程：

一开始看到左右括号，第一想到了栈。后来发现题目要求遍历所有的可能组合，第一想法是暴力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 dequeself.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)