NC26 括号生成，原思考，通过插入'()'方式显示

这个例子也是递归思想的集中体现，需要以n=1 即'()' 为起点，从0到1/2字符串长度插入'()'，并将结果回传作为下一轮递归参数。

class Solution:
    def generateParenthesis(self , n: int) -> List[str]:
        # write code here
        if n == 1: return ['()']
        pre = ['()']

        def iterate(pre, n):
            res = []
            for p in pre:
                for i in range(len(p)):
                    if p[:i]+'()'+p[i:] not in res:
                        res.append(p[:i]+'()'+p[i:])
            n-=1
            if n == 1: return res
            return iterate(res, n)

        return iterate(pre, n)