#!/usr/bin/env python3

__author__ = 'Wei Mu'

class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        
        if n == 0:
            return [""]
        
        left = n - 1
        right = n
        ans = ['(']
        
        return (self.helper_func(ans, left, right))
    
    def helper_func(self, ans, left, right):
        if left == 0 and right == 0:
            return(ans)
        
        elif left == 0:
            for i in range(len(ans)):
                ans[i] = ans[i] + right * ')'
            return(ans)
        
        elif left == right:
            for i in range(len(ans)):
                ans[i] = ans[i] + '('
            return(self.helper_func(ans, left - 1, right))
        
        else:
            temp1 = []
            temp2 = []
            for i in range(len(ans)):
                temp1.append(ans[i] + '(')
                temp2.append(ans[i] + ')')
            ans = self.helper_func(temp1, left - 1, right) + self.helper_func(temp2, left, right - 1)
            
            return(ans)
