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:

"((()))", "(()())", "(())()", "()(())", "()()()"

Hint: use recursion. Count the number of left parentheses and right parentheses respectively. Put either '(' or ')' at the current position (output[pos]), then proceed to pos+1. If number of left parentheses and number of right parentheses both equal to n, output the result.

01 public ArrayList<String> generateParenthesis(int n) {
02     ArrayList<String> results=new ArrayList<String>();
03     if(n==0)
04     {
05         results.add("");
06         return results;
07     }
08   
09     char [] output=new char[n*2];
10     generateParenthesis(results,0,0,n,0,output);
11     return results;              
12 }
13 
14 public void generateParenthesis(ArrayList<String> results, int numLeft, int numRight, int n, int pos, char [] output)
15 {
16     if(numLeft>n||numRight>numLeft)
17         return;
18     if(numLeft==n && numRight==n)
19     {
20         String out=new String(output);
21         results.add(out);
22     }
23   
24     if(numLeft<n)
25     {
26         output[pos]='(';
27         generateParenthesis(results, numLeft+1,numRight,n,pos+1,output);
28     }
29   
30     if(numRight<n)
31     {
32         output[pos]=')';
33         generateParenthesis(results, numLeft,numRight+1,n,pos+1,output);          
34     }                  
35 }