22.md

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

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

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

my thoughts:

1. build the res from n-1 's res:
n = 1:   ()
n = 2:   ()() swap first ) with later ( -> (())
n = 3:   ()()() s -> (())();  (()())  
         ()(()) s -> (()());  ((()))
		 * remove the identical ones
		 

my solution:

**********47ms
class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if n == 0:
            return []
        if n == 1:
            return ["()"]
        
        temp = ["()"+x for x in self.generateParenthesis(n-1)]
        res = set()
        for t in temp:
            res.add(t)
            ta = list(t)
            #print temp, t, ta
            ta[1] = "("
            for i in range(2,len(ta)):
                if ta[i] =="(":
                    ta[i] = ")"
                    res.add( ''.join(ta) )
                    ta[i] = "("
        return list(res)

my comments:

Do not quite get why can I just randomly select a idx from the whole list every time. Maybe it is mathmatically tested.

from other ppl's solution:

1. build it as a binary tree, 42ms:
class Solution(object):
 def generateParenthesis(self, n):
    def generate(p, left, right, parens=[]):
        if left:         generate(p + '(', left-1, right)
        if right > left: generate(p + ')', left, right-1)
        if not right:    parens += p,
        return parens
    return generate('', n, n)
	
2. more readable solution:
class Solution:
# @param {integer} n
# @return {string[]}
def generateParenthesis(self, n):
    if not n:
        return []
    left, right, ans = n, n, []
    self.dfs(left,right, ans, "")
    return ans

def dfs(self, left, right, ans, string):
    if right < left:
        return
    if not left and not right:
        ans.append(string)
        return
    if left:
        self.dfs(left-1, right, ans, string + "(")
    if right:
        self.dfs(left, right-1, ans, string + ")")