回溯法题目 leetcode

秒速五厘米 2022-12-31 01:24 187阅读 0赞

1. [22. 括号生成][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

[22.]: https://leetcode-cn.com/problems/generate-parentheses/