Generate Parentheses

Problem: Generate Parentheses

About parentheses, we can conclude that number of left parenthesis defines number of pairs of parentheses, and number of needed right parenthesis is defined by single left parenthesis. Thus, while doing backtracking, we only need to care about these two numbers.

Code in Python:

    class Solution(object):
        def generateParenthesis(self, n):
            """
            :type n: int
            :rtype: List[str]
            """
            res = []
            def generate(s, x, y):
                if x < n:
                    if not y:
                        generate(s+"(", x+1, y+1)
                    else:
                        generate(s+"(", x+1, y+1)
                        generate(s+")", x, y-1)
                if x == n:
                    if not y:
                        res.append(s)
                    else:
                        res.append(s+")"*y)

            generate("", 0, 0)
            return res

Code in Java:

public class Solution {
    public List<String> generateParenthesis(int n) {
        int left = n, right = n;
        List<String> res = new ArrayList<String>();

        helper(n, left, right, "", res);

        return res;
    }

    private void helper(int n, int l, int r, String s, List<String> res) {
        if (s.length() == n * 2) {
            res.add(s);
            return;
        }

        if (l > 0)
            helper(n, l-1, r, s+"(", res);

        if (r > 0 && r > l)
            helper(n, l, r-1, s+")", res);
    }
}