力扣刷题笔记：22.括号生成（回溯模板题，直接套模板）

ゝ一世哀愁。 2022-11-06 08:56 106阅读 0赞

## 题目： ##

22、括号生成

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

示例 1：

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

示例 2：

> 输入：n = 1  
> 输出：\["()"\]

提示：

> 1 <= n <= 8

## 题解思路： ##

直接套回溯法模板，再定义个判断括号有效的函数即可。

> 回溯python模板：[https://blog.csdn.net/weixin\_44414948/article/details/114489545][https_blog.csdn.net_weixin_44414948_article_details_114489545]

## 题解python代码： ##

class Solution:
        def generateParenthesis(self, n: int) -> List[str]:
            if not n:
                return list()    
            T = ["(", ")"]
            res = []
            path = []
    
            def valid(s: str):
                count = 0
                for a in s:
                    if count<0: return False
                    if a=="(": count+=1
                    else: count -= 1
                return count==0
    
            def backtrack(index: int):
                if index==2*n:
                    t = "".join(path)
                    if valid(t):
                        res.append(t)
                    return
                for ch in T:
                    path.append(ch)
                    backtrack(index+1)
                    path.pop()
            
            backtrack(0)
            return res

> 作者：a-qing-ge  
> 链接：[https://leetcode-cn.com/problems/generate-parentheses/solution/hui-su-mo-ban-ti-by-a-qing-ge-njqe/][https_leetcode-cn.com_problems_generate-parentheses_solution_hui-su-mo-ban-ti-by-a-qing-ge-njqe]  
> 来源：力扣（LeetCode）[https://leetcode-cn.com/problems/generate-parentheses/][https_leetcode-cn.com_problems_generate-parentheses]

[https_blog.csdn.net_weixin_44414948_article_details_114489545]: https://blog.csdn.net/weixin_44414948/article/details/114489545
[https_leetcode-cn.com_problems_generate-parentheses_solution_hui-su-mo-ban-ti-by-a-qing-ge-njqe]: https://leetcode-cn.com/problems/generate-parentheses/solution/hui-su-mo-ban-ti-by-a-qing-ge-njqe/
[https_leetcode-cn.com_problems_generate-parentheses]: https://leetcode-cn.com/problems/generate-parentheses/