Skip to content

22. Generate Parentheses

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

c++
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        next(n, n, "", result);
        return result;
    }

    void next(int l, int r, string s, vector<string>& res) {
        if (r < l) {
            return;
        }
        if (l == 0 && r == 0) {
            res.emplace_back(s);
            return;
        }
        if (l > 0) {
            next(l - 1, r, s + "(", res);
        }
        if (r > 0) {
            next(l, r - 1, s + ")", res);
        }
    }
};
go
func next(l int, r int, s string, res []string) []string {
  if r < l {
    return res
  }
  if l == 0 && r == 0 {
    return append(res, s)
  }
  if l > 0 {
    res = next(l-1, r, s+"(", res)
  }
  if r > 0 {
    res = next(l, r-1, s+")", res)
  }
  return res
}

func generateParenthesis(n int) []string {
  return next(n, n, "", []string{})
}
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)