Generate Parentheses

Problem

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

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

Solution

Backtracking Solution

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

    private void helper(List<String> res, String s, int left, int right, int n) {
        if (s.length() == n * 2) {
            res.add(s);
            return;
        }
        if (left < n) helper(res, s + "(", left + 1, right, n);
        if (right < left) helper(res, s + ")", left, right + 1, n); //Not right < n !
    }
}

Analysis

Entry level of applying backtracking
Since the valid parentheses must have "(" first, we start by recursively calling helper() with adding s + "(" and pass left + 1
Then we add ")" as long as right < left
We return the method when s.length() == 2 * n