【算法题】22.括号生成-力扣(LeetCode)
1.题目
下方是力扣官方题目的地址
数字 n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入:n = 1
输出:["()"]
提示:
1 <= n <= 8
2.题解
该题我采用深度优先搜索中的回溯和剪枝
思路
这些组合就两种情况,一种是“(”,一种是“)”,可以很容易想到二叉树,而二叉树可以想到深度优先搜索,而这题的深度优先有要求,就是“(”后面必须要有“)”,不能是“)(”这样的形式。
我们观察发现,符合条件的组合必须得满足两个条件:
-
1.括号必须两两配对
-
2.在选择括号进行组合时,“)”的次数始终不能大于“(”的次数,比如说
第一次选择的时候选了")",那么当前的")"的个数已经大于了"("的个数,所以后面的就不用选了,直接剪掉。
为了方便理解,我粗略地画了一张图,表示n=2时,也就是有四层的二叉树,红色的表示不符合条件被剪枝的
Python代码
class Solution(object):
def generateParenthesis(self, n):
global s
"""
:type n: int
:rtype: List[str]
"""
ans,s=[],''
def dfs(d,l,r): # d表示二叉树的深度,l,r分别表示选择到当前层时"("和")"的个数
global s
if l>n or r>l:return # 剪枝 不符合前文所说的两种条件时直接return剪掉
if d==2*n:
ans.append(s) # 如果搜索到了最底层,那一定是符合条件的,添加到ans中去,然后停止
return
s+='('
dfs(d+1,l+1,r)
s=s[:-1] # 二叉树搜索的基本方法
s+=')'
dfs(d+1,l,r+1)
s=s[:-1] # 回溯
dfs(0,0,0)
return ans
3.结语
本人资历尚浅,发博客主要是记录与学习,欢迎大佬们批评指教!大家也可以在评论区多多交流,相互学习,共同成长。
标签:剪枝,return,22,dfs,力扣,括号,二叉树,ans,LeetCode From: https://blog.csdn.net/Janium/article/details/142112103