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

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

• 1 <= n <= 8

Try this Problem on your own or check similar problems:

1. Valid Parentheses
2. Letter Combinations of a Phone Number

Solution:

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

    private void helper(StringBuilder current, int left, int right, List<String> result){
        if(left == 0 && right == 0){
            result.add(current.toString());
            return;
        }

        if(left > 0) {
            current.append("(");
            helper(current, left - 1, right, result);
            current.setLength(current.length()-1);
        }
        if(right > left){
            current.append(")");
            helper(current, left, right - 1, result);
            current.setLength(current.length()-1);
        }
    }
}

Time/Space Complexity:

• Time Complexity: O(n*4^n/sqrt(n))
• Space Complexity: O(n*4^n/sqrt(n))

Explanation:

It’s not a trivial backtracking problem. Notice that we have to generate string with n*2 length, with the same number of ( and ). So initially we have n of ( and n of ) available, we add ( until there is no more to add, and then add ) until right == left (notice that at any point if we have something like ()), it’s impossible to have a valid combination of parentheses, since we can’t close the last )). We make sure that we always more or equal number of left parentheses used than the right ones. We use Stringbuilder because it’s more robust and faster than passing string by value to the recursive calls. Since it’s a backtracking problem after each recursive call we remove the element that we have chosen before the call. The time and space complexity match n-th Catalan number, but on the interview you could probably come with less restrictive boundary like O(n*2^n) (the n multiplier is used for creating new string from the stringbuilder).