回溯法 题目 leetcode

1. 22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

方法1: 回溯法， 学习记忆

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        # 回溯法 掌握的不好，对这类问题 进行归总 学习记忆

        ans = []
        # 通过控制 左 右括号的 数量 来生成 有效的括号序列
        def generatePa(S, left, right):
            if len(S) == 2*n:
                ans.append(''.join(S))  # 字符串
                return 
            if left < n:
                S.append('(')
                generatePa(S, left+1, right)
                S.pop()
            if right < left:
                S.append(')')
                generatePa(S, left, right+1)
                S.pop()

        generatePa([], 0, 0)
        return ans

方法2:  生成所有可能，在判断是否有效

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        # 1. 先生成所有可能组合， 然后验证有效的；
        ans = []
        def generatep(S):
            if len(S)==2*n: # 递归结束条件
                if valid(S):
                    ans.append(''.join(S))
                return 
            S.append('(') # 生成 所有可能结果代码 递归 仔细学习
            generatep(S)
            S.pop()
            S.append(')')
            generatep(S)
            S.pop()
        def valid(S):
            temp = 0
            for c in S:
                if c == '(':
                    temp += 1
                else:
                    temp -= 1
                if temp < 0:
                    return False
            return temp == 0
        generatep([])
        return ans