Generate Parentheses

Question: 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:

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

You may view the full question here.

Approach 1: Of course, my initial instinct was to formulate a universal list of all possible combinations of the parentheses and then, filter out only the ones that form a valid pattern. In short — Brute Force!

That definitely did not sound exciting, and moreover sounded quite painful to execute. So, the next option was a few clicks and scrolls away. You may view the full solution and other alternate approaches here.

This next approach is heavily inspired by/borrowed from the actual solution posted on LeetCode. Here, our primary goal is to restrict ourselves to formulate only valid patterns. To do so, here are a few observations/pointers we keep in mind in the process —

• The pattern always starts with an opening parenthesis “(”
• The pattern always ends with a closing parenthesis “)”
• While forming the pattern, the number of opening parentheses is always greater than or equal to the number of closing parentheses

Now, let’s look at an implementation using recursion —

//Approach 1
//Runtime: 1ms
//Memory usage: 37.8MB
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        formValidPattern(result, "(", 1, 0, n);
        return result;
    }
    
    private void formValidPattern(List<String> result, String currPat, int open, int close, int max){
        if(open==max && close==max-1){
            result.add(currPat+")");
            return;
        }
        
        if(open<max){
            formValidPattern(result, currPat+"(", open+1, close, max);
        }
        if(close<max && (close+1)<=open){
            formValidPattern(result, currPat+")", open, close+1, max);
        }
        return;
    }
}

Find more posts here.

Cheers & Chao!