/**

 * 功能：打印n对括号的所有有效组合（即左右括号正确配对）。

*/

两种方法：

方法一:

	/**

	 * 思路：在括号的最前面或者原有的每对括号中面插入一对括号。

至于其它任何位置。比方字符串的末尾，都会跟之前的情况反复。

	 * 注意：将字符串放进结果列表之前。必须检查列表有无反复。

	 * @param remaining

	 * @return

	 */

	public static HashSet<String> generateParens(int remaining){

		HashSet<String> set=new HashSet<String>();

		if(remaining==0)

			set.add("");

		else{

			HashSet<String> prev=generateParens(remaining-1);

			for(String str:prev){

				//括号内插入

				for(int i=0;i<str.length();i++){

					if(str.charAt(i)=='('){

						String s=insertInside(str,i);

						set.add(s);//插入元素之前,HashSet会自己主动检查有无反复

					}

				}

				//括号最前面插入

				if(!set.contains("()"+str))

					set.add("()"+str);

			}

		}

		return set;

	}

	/**

	 * 在每对括号内插入

	 * @param str

	 * @param leftIndex

	 * @return

	 */

	public static String insertInside(String str,int leftIndex){

		String left=str.substring(0,leftIndex+1);//左括号之后插入括号，所以须要leftIndex+1

		String right=str.substring(leftIndex+1);

		return left+"()"+right;

	}

方法二：

	/**

	 * 思路：从头開始构造字符串，避免出现反复字符串。注意增加左括号和右括号，仅仅要字符串仍然有效。

	 * 每次递归调用，都有一个索引指向字符串的某个字符。选择左括号和右括号：

	 * 		1）左括号：仅仅要左括号还没实用完，就能够插入左括号。

* 		2）右括号：仅仅要不造成语法错误，就能够插入右括号（右括号比左括号多。即语法错误）。

	 * 因此。仅仅需记录同意插入的左右括号数目。假设还有左括号可用。就插入一个左括号。然后递归。

	 * 假设后括号比左括号多，（即使用中的左括号比右括号多）。就插入一个右括号，然后递归。

*

	 * 在字符串的每个索引相应位置插入左括号和右括号。并且绝对不会反复索引！！！

	 * @param count

	 * @return

	 */

	public static ArrayList<String> generateParens2(int count){

		ArrayList<String> list=new ArrayList<String>();

		char[] str=new char[count*2];

		addParens(list,count,count,str,0);

		return list;

	}

	public static void addParens(ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) {

		// TODO Auto-generated method stub

		if(leftRem<0||rightRem<leftRem)

			return;

		if(leftRem==0&&rightRem==0){

			String s=String.copyValueOf(str);

			list.add(s);

		}

		if(leftRem>0){

			str[count]='(';

			addParens(list, leftRem-1, rightRem, str, count+1);

		}

		if(rightRem>leftRem){

			str[count]=')';

			addParens(list, leftRem, rightRem-1, str, count+1);

		}

	}