22. Generate Parentheses

# Medium

Find the discipline.

No more ')' following than unpairing '(' in string. Use stack to help pairing, only unpairing '(' are stored in stack.

Solution:

Use helper function to help iteration.

Python

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """

        result = []
        stack = []   # help pairing, only store unpairing '('
        s = "("
        stack.append('(')
        l_count = n-1   # number of left braket usable
        r_count = n    # number of right braket usable
        self.helper(s, stack, result, l_count, r_count)
        
        return result
    
    def helper(self, s, stack, result, l_count, r_count):
        # stop condition
        if r_count == 0:
            if len(stack) == 0:  # valid string
                result.append(s)
            return

        # regular case
        if len(stack) != 0:
            if l_count > 0:
                # append '(', then add it to stack
                stack.append('(')
                temp = stack[:]  # 非常关键的一步，一定要深度复制，不然stack随时在改变，影响下一步的stack.pop()
                self.helper(s+'(', temp, result, l_count-1, r_count)
                stack.pop()
                # append ')', then eliminate one '(' from stack
                stack.pop()
                self.helper(s+')', stack, result, l_count, r_count-1)
            else:
                stack.pop()
                self.helper(s+')', stack, result, l_count, r_count-1)
        else:
            if l_count > 0:
                stack.append('(')
                self.helper(s+'(', stack, result, l_count-1, r_count)
                
        

为了不影响再次利用stack，迭代的时候用其深度复制的temp传参，并记得再次利用前先要pop出去最后一个元素

Time complexity = $O(2^{2n-1})$ , space complexity = $O(2^{2n})$ , 因为每个位置最多有2选择。