題目

給出 n 代表生成括號的對數(shù)，請你寫出一個函數(shù)，使其能夠生成所有可能的并且有效的括號組合。

例如，給出 n = 3，生成結(jié)果為：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

思路

遞歸法

1、def dfs(res, string, n, l, r):，遞歸函數(shù)的參數(shù)意義分別為，返回用的結(jié)果列表res，當(dāng)前括號匹配字符串string，括號對數(shù)n，目前左括號數(shù)l，目前右括號數(shù)r。
2、左括號數(shù)等于括號對數(shù)時，只需加入剩余右括號，當(dāng)前匹配字符串括號匹配結(jié)束，加入res。
3、左括號等于右括號或者當(dāng)前一個括號也沒有時只能加入左括號，并把左括號數(shù)+1。
4、其他情況既能加入左括號又能加入右括號，且把相應(yīng)的符號數(shù)+1。

回溯法

1、基礎(chǔ)字符串為'((()))'
2、遍歷字符串，當(dāng)字符串中存在一個右括號位置為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)注我的公眾號

半畝房頂