括号生成

22. 括号生成 - 力扣（LeetCode）

问题简述

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

思路

• 相当于对 ['(', ')'] 进行深度优先遍历；

• 通过剪枝排除无效情况；

  

  回溯算法（深度优先遍历）+ 广度优先遍历（Java） - liweiwei1419

Python（写法 1）

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        ret = []

        def dfs(l, r, tmp):
            # 非法情况（剪枝）
            if l < r or l > n:  # 已经包括 r > n
                return

            if l == r == n:
                ret.append(''.join(tmp))
                return
            
            # 先添加左括号
            tmp.append('(')
            dfs(l + 1, r, tmp)
            tmp.pop()

            # 再添加右括号
            tmp.append(')')
            dfs(l, r + 1, tmp)
            tmp.pop()

        dfs(0, 0, [])
        return ret

Python（写法 2，写法 1 的等价写法）

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        ret = []

        def dfs(l, r, tmp):
            # 非法情况
            if l < r or l > n:  # 已经包括 r > n
                return

            if l == r == n:
                ret.append(''.join(tmp))
                return
            
            for c in '()':
                # 注意 l 和 r 也要回溯，这里直接传表达式可以省略这一步；
                # 同样，如果不用 tmp 数组，而是传字符串表达式，那么 tmp 的回溯也可以省略（写法3）
                # if c == '(': l += 1
                # else: r += 1
                tmp.append(c)
                dfs(l + 1 if c == '(' else l, 
                    r + 1 if c == ')' else r, 
                    tmp)
                tmp.pop()
                # if c == '(': l -= 1
                # else: r -= 1

        dfs(0, 0, [])
        return ret

Python（写法 3，不回溯）

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        ret = []

        def dfs(l, r, tmp):
            # 非法情况
            if l < r or l > n:  # 已经包括 r > n
                return

            if l == r == n:
                ret.append(tmp)
                return

            for c in '()':
                # 不回溯的写法
                dfs(l + 1 if c == '(' else l, 
                    r + 1 if c == ')' else r, 
                    tmp + c)

        dfs(0, 0, '')
        return ret