構造n個成對括号

Generate Parentheses

• 給出一個整數n，實作一個函數生成n對小括号，n對小括号的左右括弧順序不限，但應該閉合。
• Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

example 1

For example, given n = 3, a solution set is:

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

思路

1. n=2

   的情況為

   n=1

   時的括号串

   ()

   中在縫隙位置再插入一個括号，如

   1(2)3

   中

   1,2,3

   位置。可以用

   set

   剔除重複元素。
2. 遞歸解決，

   n=3

   時為在

   ()()

   和

   (())

   中再插入一個括号。
3. 思路2來源自leetcode讨論區，使用open記錄已經有多少左括号，如果n==0，将

   ")" * open

   閉合。

代碼

class Solution(object):

    def __init__(self):
        self.table = {1: ['()']}

    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if n == 1:
            return self.table[1]
        if n-1 in self.table.keys():
            nset = set()
            n1set = self.table[n-1]
            for _, item in enumerate(n1set):
                for j in range(len(item)):
                    nset.add(item[0:j] + '()' + item[j:])
            self.table[n] = list(nset)
            return self.table[n]
        else:
            self.generateParenthesis(n-1)
            return self.generateParenthesis(n)


    def gen2(self, n, open=0):
        if n == 0: return [')'*open]
        if open == 0:
            return ['('+x for x in self.gen2(n-1, 1)]
        else:
            return [')'+x for x in self.gen2(n, open-1)] + ['('+x for x in self.gen2(n-1, open+1)]
           

本題以及其它leetcode題目代碼github位址: github位址