括号排列问题

给出n对括号，求括号排列的所有可能性。

java源码：

package myself;

import java.util.ArrayList;
import java.util.Scanner;

public class ArrangementOfBrackets {

	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		System.out.println("输入括号的对数：");
		int n=scanner.nextInt();
		int leftNum=n,rightNum=n;//左括号和右括号都各有n个
        //用于存放解空间
		ArrayList<String>results=new ArrayList<String>();
		parentheses("",results,leftNum,rightNum);
		for(String s:results) {
			System.out.println(s);
		}
	}

	private static void parentheses(String sublist, ArrayList<String> results, int leftNum, int rightNum) {
		if(leftNum==0&&rightNum==0) {
			results.add(sublist);
		}
		//选择和条件。对于不同的if顺序，输出的结果顺序是不一样的，但是构成一样的解空间
		if(rightNum>leftNum) {
			parentheses(sublist+")", results, leftNum, rightNum-1);
		}
		if(leftNum>0) {
			parentheses(sublist+"(", results, leftNum-1, rightNum);
		}
		
	}

}

运行结果：

利用回溯思想：

1、用了一个空字符串来作为临时变量存储不完整解；

2、用了一个ArrayList<String> results来存放符合要求的解。在后面可以看到，不一定要这样做，也可以直接打印结果；

3、把leftnum和rightnum传入给递归函数，这样可以用于判断结束条件；

4、由于使用了两个if，所以当一次递归退出后，例如从第一个if退出，第二个递归直接递归的是leftnum-1和rightnum，这其实是已经恢复状态了（如果没有恢复状态，那就是leftnum, rightnum-1）。