Skip to content

22. Generate Parentheses

https://leetcode.com/problems/generate-parentheses/

js
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
  var result = []
  next(n, n, '', result)
  return result

  function next(l, r, s, res) {
    if (r < l) {
      return
    }
    if (l === 0 && r === 0) {
      res.push(s)
    }
    if (l > 0) {
      next(l - 1, r, s + '(', res)
    }
    if (r > 0) {
      next(l, r - 1, s + ')', res)
    }
  }
}
py
class Solution(object):

    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        result = []
        self.next(n, n, '', result)
        return result

    def next(self, l, r, s, res):
        if r < l:
            return
        if l == 0 and r == 0:
            res.append(s)
        if l > 0:
            self.next(l - 1, r, s + '(', res)
        if r > 0:
            self.next(l, r - 1, s + ')', res)