22.Generate Parentheses

Givennpairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, givenn= 3, a solution set is:

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

Method 1 DFS + backtrack, O (n!) time, O(2^n) space

• keep track of number of open and close parentheses available.
  • always backtrack open parenthese if > 0
  • only backtrack close parenthese if it's > open parentheses.

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        result = []
        self.backtrack(result, "", n, n)
        return result

    def backtrack(self, result, string, left, right):
        if left == 0 and right == 0:
            return result.append(string)
        if left >= 0:
            self.backtrack(result, string+'(', left-1, right)
        if right > left:
            self.backtrack(result, string+')', left, right-1)