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:

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

心得：

我靠，这道题自己做的时候就想着用深度递归啊n叉树啊，完全不会去想左括号和右括号谁多谁少的问题，做死了去都不对。

发现规律竟然这么简介明了，

1.左括号大于右括号的时候可以加左和右括号，

2.左括号等于右括号时只能加左括号

3.左括号永远都不会小于右括号

4当右括号等于n时就添加到list里

5.当左括号等于n时就只能加右括号

总结，做了这么几十到编程题，分类中我觉得查询真的是最难的。

import java.util.ArrayList;
public class Solution {
    ArrayList<String> list = new ArrayList<String>();
	
	public ArrayList<String> generateParenthesis(int n) {
		if(n<=0) {
			return new ArrayList<String>();
		}
		String s="";
		help(n, n, s);
        return list;
    }
	
	public void help(int x,int y,String s) {
		if(x==0&&y==0) {
			list.add(s);
			return;
		}
		if(x==0&&y>0) {
			help(x, y-1, s+")");
			return;
		}
		
		if(x==y) {
			help(x-1, y, s+"(");
			return;
		}
		if(x<y) {
			help(x-1, y, s+"(");
			help(x, y-1, s+")");
			return;
		}
		
	}
}