[数据结构与算法]算法很美：合法括号

题目描述

• 合法括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合

分析

• 对所有情况进行枚举，即在上一层结果的基础上，进行“左”、“右”、“包”

代码

	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		Set<String> solve = solve(n);
		//Set<String> solve2 = solve2(n);
		System.out.println(solve.toString());
		//System.out.println(solve2.toString());
	}
	
	
	//递归式
	private static Set<String> solve2(int n) {
		//set天生去除重复
		Set<String> resSet=new HashSet<>();
		if(n==0) return resSet;
		if(n==1) {
			resSet.add("()");
			return resSet;
		}
	
		Set<String>  res_n_1 = solve(n-1);
		
		for (String s : res_n_1) {
			resSet.add(s+"()");
			resSet.add("()"+s);
			resSet.add("("+s+")");
		}
		
		return resSet;
		
	}
	
	
	//迭代形式适用于n特别大
	private static Set<String> solve(int n) {
		//set天生去除重复
		Set<String> resSet=new HashSet<>();
		if(n==0) return resSet;
		
		resSet.add("()");
		
		
		//当n>=2时以左右包，开始对每个对象进行处理
		for (int i = 2; i <=n; i++) {
			Set<String> res_newSet=new HashSet<>();
			for (String s : resSet) {
				res_newSet.add("()"+s);
				res_newSet.add(s+"()");
				res_newSet.add("("+s+")");
			}
			
			resSet=res_newSet;
		}
		
		return resSet;
		
	}