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 n
            if 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 res


class 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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59