LeetCode-面试题 08.09-括号

原题链接：https://leetcode-cn.com/problems/bracket-lcci/

括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。
说明：解集不能包含重复的子集。
例如，给出 n = 3，生成结果为：

解题思路：

1. 终止条件 len(path)==2n，即遍历过的括号用path存储，长度等于2n时结束；
2. 当剩余的括号中左括号数大于0时，可以选择加入path；
3. 而剩余的括号中右括号数不得小于左括号数，即当剩余括号中右括号数大于左括号数，可以选择右括号加入path。

Python3代码：

  class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def func(Lremain, Rremain, path):
            if len(path) == n*2:
                res.append(path)
                return 
            if Lremain > 0:
                func(Lremain-1, Rremain, path+'(')
            if Lremain < Rremain:
                func(Lremain, Rremain-1, path+')')
        func(n, n, '')
        return res