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;
		}
		
	}
}