Generate Parentheses

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: {((())), (()()), (())(), ()(()), ()()()}

How do we solve this problem? Let’s start with base cases.

• n=0 : result set is empty (no solution)
• n=1 : result set is {()}

For n=2, we can construct the result set by inserting a new pair “()” into all gaps in the each of the result from n=1. For example, for n=1 result = {()} that has only one solution () that has total 3 gaps as follows –

      (  )
     ^  ^  ^
    g1  g2  g3

So, In order to get result for n=2 we will append () in each gap of each of the solutions of n=1 as follows –

     ()()         (())       ()()
     ^             ^           ^
    g1             g2          g3 

The final result set (unique elements) for n=2 would be {()(), (())}.

So, in general there are m+1 gaps in a parenthesis of length m. So, we can construct the string with n parenthesis by inserting “()” into each of the m+1 gaps of the each of the solution of length m in result set for n-1.

How to implement this? We can formulate this problem as a Tree traversal problem where starting from n=1 as root “()” we traverse m+1=2+1=3 children corresponding to the string constructed by inserting “()” into each of the m+1 gaps. So, nodes at a level n of this tree will contain all possible strings with n pair of parenthesis. For

 
                        ( )           <- n = 1
                   /     |    \ 
            ( ) ( )   (())   ()()     <- n = 2
           / |  \ \ \      
     ()()() (())()     .........      <- n = 3

So, we can do a level order traversal using a queue and stop at level = n at which point the queue will contains the result set for n. Please read my previous post to understand the algorithm for level order traversal using queue. Below is a simple implementation of this idea.

public static ArrayList<String> genParanthesis(int n){
	ArrayList<String> res = new ArrayList<String>();
	if(n <= 0){
		return res;
	}
	if(n == 1){
		res.add("()");
		return res;
	}
	
	Queue<StringBuilder> queue = new ArrayDeque<StringBuilder>();
	Set<String> visited = new HashSet<String>();
	queue.add(new StringBuilder("()"));
	int count = 1;
	int level = 1;
	
	//do a level order (BFS) trversal upto level=n
	while(!queue.isEmpty()){
		StringBuilder node = queue.poll();
		String cur = node.toString();
		count--;
		visited.add(cur);
		
		//at the end of level order traversal upto level n the queue will contain all the leaves at level n
		//which are basically all possible strings constructed with n pair of parenthesis
		if(level == n){
			res.add(cur);
			continue;
		}
		
		//if not reached level n yet, then do BFS level order
		//there are total 1+len(cur) gaps
		for(int gap = 0; gap < cur.length()+1; gap++){
			//we create a child by putting () to each of the gap positions
			StringBuilder child = new StringBuilder(cur).insert(gap, "()");
			if(!visited.contains(child.toString())){
				queue.add(child);
				visited.add(child.toString());
			}
		}
		
		//end of a level
		if(count == 0){
			level++;
			count = queue.size();
		}
	}
	
	return res;
}

Alternative Recursive Approach
The idea is to keep two counters, one for number of remaining left parenthesis and the other for total number of remaining right parenthesis to be added. Each time we add a right parenthesis if remaining is greater than 0. We also balance it by adding left parenthesis only if remaining right is greater than 0. Below is the implementation of this algorithm.

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

public void generate(String str, int left, int right, ArrayList<String> res){
    if(right == 0 && left == 0){
        res.add(str);
    }
    
    if(right > 0){
        generate(str+")", left, right-1, res);
    }
    if(left > 0){
        generate(str+"(", left-1, right+1, res);
    }
}