22 括号生成

 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
60
61
62

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
## 回溯算法

from collections import Counter


class Solution:
    def generateParenthesis(self, n: int):
        self.n = n
        # 结果
        result = []
        # 每次运行的
        track = []
        tmp = []

        def backtrack(path, options):
            if len(path) == n * 2:
                tmp.append(path)
                result.append(''.join(path))
                return

            for i in range(len(options)):
                if not self.isvalid(path, options[i]):
                    continue
                path.append(options[i])

                backtrack(path, options)

                path.pop()

        backtrack(track, ['(', ')'])
        return result

    def isvalid(self, path, next):
        if len(path) == 0 and next == ')':
            return False

        count_dict = Counter(path)
        left_value = count_dict['(']
        right_value = count_dict[')']
        if next == ')' and right_value + 1 > left_value:
            return False

        for key, value in count_dict.items():
            if key == next and value == self.n:
                return False

        return True


if __name__ == '__main__':
    solution = Solution()
    result = solution.generateParenthesis(3)
    print(result)