cc150_9_6.java

import java.util.ArrayList;


public class Q9_6 {
	
	
	public void addParen(ArrayList<String> list,int left, int right, char[] str, int cnt){
		if(left < 0 || right < left) return;
		
		if(right == 0 && left == 0){
			String rst_s = String.copyValueOf(str);
			list.add(rst_s);
		}
		else if(left > 0){
			str[cnt] = '(';
			addParen(list, left -1, right, str, cnt +1);
			
		}
		
		if(right > left){
			str[cnt] = ')';
			addParen(list, left,right-1,str,cnt+1);
		}
		
	}
	
	public ArrayList<String> insertParens(int cnt){
		char[] str = new char[cnt*2];
		ArrayList<String> list = new ArrayList<String>();
		addParen(list,cnt,cnt,str,0);
		return list;
	} 
	
	
	public static void main(String[] args){
		Q9_6 test = new Q9_6();
		System.out.println(test.insertParens(6));
	}

}