Generate Parentheses

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

How to Solve

Approach 1

To generate all sequences, we use a recursion. All sequences of length n is just ( plus all sequences of length n-1, and then ) plus all sequences of length n-1.

To check whether a sequence is valid, we keep track of balance, the net number of opening brackets minus closing brackets. If it falls below zero at any time, or doesn’t end in zero, the sequence is invalid - otherwise it is valid.

Approach 2

Instead of adding ‘(‘ or ‘)’ every time as in Approach 1, let’s only add them when we know it will remain a valid sequence. We can do this by keeping track of the number of opening and closing brackets we have placed so far.

We can start an opening bracket if we still have one (of n) left to place. And we can start a closing bracket if it would not exceed the number of opening brackets.

Test Cases

Input:

(int) n = 3

Output:

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

Solution

Java

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

    private void backtrack(int n, List<String> res, StringBuilder sb, int open, int close) {
        if (sb.length() == n*2) {
            res.add(sb.toString());
            return;
        }

        if (open < n) {
            sb.append('(');
            backtrack(n, res, sb, open+1, close);
            sb.deleteCharAt(sb.length() - 1);
        }

        if (close < open) {
            sb.append(')');
            backtrack(n, res, sb, open, close+1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}