題目
給出 n 代表生成括號的對數(shù)撇贺，請你寫出一個函數(shù)巡莹，使其能夠生成所有可能的并且有效的括號組合司志。
例如，給出 n = 3降宅，生成結(jié)果為：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
思路
遞歸法
1骂远、def dfs(res, string, n, l, r):，遞歸函數(shù)的參數(shù)意義分別為腰根，返回用的結(jié)果列表res激才，當前括號匹配字符串string，括號對數(shù)n额嘿，目前左括號數(shù)l瘸恼，目前右括號數(shù)r。
2册养、左括號數(shù)等于括號對數(shù)時东帅，只需加入剩余右括號，當前匹配字符串括號匹配結(jié)束球拦，加入res靠闭。
3邓夕、左括號等于右括號或者當前一個括號也沒有時只能加入左括號，并把左括號數(shù)+1阎毅。
4、其他情況既能加入左括號又能加入右括號点弯，且把相應(yīng)的符號數(shù)+1扇调。
回溯法
1、基礎(chǔ)字符串為'((()))'
2抢肛、遍歷字符串狼钮，當字符串中存在一個右括號位置為i，而且滿足捡絮，0到i的字符串中熬芜，左括號數(shù)大于右括號數(shù)、第i-1位置是左括號時福稳，將i-1與i位置的括號互換（即一組左右括號互換）
代碼
//遞歸法
class Solution:
def generateParenthesis(self, n):
res = []
def dfs(res, string, n, l, r):
if l == n:
for i in range(r, n):
string += ')'
res.append(string)
return
elif l == 0 or l == r:
string +='('
dfs(res, string, n, l + 1, r)
else:
dfs(res, string + ')', n, l, r + 1)
dfs(res, string + '(', n, l + 1, r)
dfs(res, '', n, 0, 0)
return res
//回溯法
class Solution(object):
result_list = []
def generateParenthesis(self, n):
global result_list
def generate(s):
global result_list
new_s = s
left = right = 0
for i in range(n * 2):
if s[i] == '(':
left += 1
else:
right += 1
if left > right and s[i - 1] == '(':
new_s = s[:i - 1] + s[i:i + 1] + s[i - 1:i] + s[i + 1:]
if new_s not in result_list:
result_list += [new_s]
generate(new_s)
s = '(' * n + ')' * n
result_list = [s]
generate(s)
return result_list
以上
歡迎大家關(guān)注我的公眾號
半畝房頂
