22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

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

Solution

(1) Java

class Solution {

    public List<String> generateParenthesis(int n) {
        List<String> rst = new ArrayList<>();
        if (n <= 0) {
            return rst;
        }
        helper(rst, n, n, "");
        return rst;
    }

    private void helper(List<String> rst, int left, int right, String str) {
        if (left == 0 && right == 0) {
            rst.add(str);
            return;
        }
        if (right < left) {
            return;
        }
        if (left > 0) {
            helper(rst, left-1, right, str+"(");
        }
        helper(rst, left, right-1, str+")");
    }
}

(2) Python

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        rst = []
        def helper(left,right,str):
            if not left and not right:
                rst.append(str)
            if left:
                helper(left-1, right, str+"(")
            if right > left:
                helper(left, right-1, str+")")

        if not n:
            return rst

(3) Scala

object Solution {
    import scala.collection.mutable.ListBuffer
    def generateParenthesis(n: Int): List[String] = {

        if (n <= 0) {
            return List[String]()
        }
        var list = ListBuffer[String]();
        helper(list, n, n, "")
        return list.toList
    }

    def helper(list: ListBuffer[String], left: Int, right: Int, str: String): Unit = {
        if (left == 0 && right == 0) {
            list += str
            return
        }
        if (left > 0) {
            helper(list, left-1, right, str+"(")
        }
        if (right > left) {
            helper(list, left, right-1, str+")")
        }
    }
}