LeetCode22. 括号生成（剪枝）

题目描述

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

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

思路

简单利用递归搜索 a²ⁿ 次方次搜索，再进行去重和Valid验证，
改进：剪枝，在分叉之前剪枝、黑色虚线部分。（如条件：左括号>3，一开始就是右括号（left<right），右括号>3等），缩减递归次数，时间复杂度为O(2ⁿ)

解题

class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        self.list = []
        self._gen(0,0,n,"")
        return self.list
	# 辅助递归函数
    def _gen(self, left ,right , n , result):
        if left == n and right == n:
            print(result)
            self.list.append(result)
            return
        if left < n:
            self._gen(left+1, right, n ,result+ "(")
        if left > right and right < n:
            self._gen(left, right+1,n ,result+")")

提交记录

执行用时: 48 ms, 在Generate Parentheses的Python3提交中击败了96.59% 的用户