#18

#18

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

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：

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

提示：

1 <= n <= 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
 

思路：

该题是熟悉的暴力求解但不知道循环次数的题，因此可以采用dfs暴力求解的方法，形式上可以采用递归。

代码：

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def isvalid(s:str):
            k=s
            while "()" in k:
                k=k.replace("()",'')
            return k == ""
        ans=[]
        def dfs(s:list,n:int):
            if len(s)==2*n:
                s=''.join(s)
                if isvalid(s):
                    ans.append(s)
                else:
                    return
            else:
                s.append("(")
                dfs(s,n)
                s.pop()
                s.append(")")
                dfs(s,n)
                s.pop()
        s=[]
        dfs(s,n)
        return ans

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def isvalid(s:str):
            k=s
            while "()" in k:
                k=k.replace("()",'')
            return k == ""
        ans=[]
        def dfs(s:list,n:int):
            if len(s)==2*n:
                s=''.join(s)
                if isvalid(s):
                    ans.append(s)
                else:
                    return
            else:

                h=s.copy()
                h.append("(")
                dfs(h,n)
                h.pop()
                h.append(")")
                dfs(h,n)
        s=[]
        dfs(s,n)
        return ans

上方为正确答案，下面看一个错误例子。

n=3

def isvalid(s: str):
    k = s
    while "()" in k:
        k = k.replace("()", '')
    return k == ""

ans = []

def dfs(s: str, n: int):
    if len(s) == 2 *n:
        s = ''.join(s)
        print(s)
        if isvalid(s):
            ans.append(s)
    else:
        s.append("(")
        dfs(s, n)
        s.pop()
        s.append(")")
        dfs(s, n)

s = []
dfs(s, n)
print(ans)

其中，这段代码的输出ans为空，我想了许久，发现python中，列表之间的直接赋值是地址传递，即递归中调用dfs，dfs中会把s给修改了，因此，有两种解法。

一种是利用python中copy函数，有意识地将地址传递变为值传递。

另一种是利用递归函数的特点，即用即仍，每次递归结束把该结果丢掉就可。