[LeetCode]Generate Parentheses

题目：给定一个数字n，求出组成n对括号的可能字符串

算法：利用栈匹配括号

1. "(", 直接将"("压入栈、 字符串中
2. ")", 若栈顶是"(", 则弹出栈顶元素。并将")"增加字符串中

public class Solution {
    private List<String> parenthesesList = new ArrayList<String>(); 
		
	    public List<String> generateParenthesis(int n) {
	        Stack<String> stack = new Stack<String>();
	        dfs(stack, "", n);
	        return parenthesesList;
	    }
	    
	    /**
	     * Algorithm:
	     * 
	     * 1. Add "(", stack push "(" directly
	     * 2. Add ")", if the top of stack is "(", pop it
	     * 
	     */
	    public void dfs(Stack<String> stack, String parentheses, int nParentheses) {
	    	if (parentheses.length() >= nParentheses*2) {
	    		if (parentheses.length()==nParentheses*2 && stack.empty()) {
	    			parenthesesList.add(parentheses);
	    		}
	    		return ;
	    	}
	    	
	    	// push "("
	    	stack.push("(");
	    	dfs(stack, parentheses+"(", nParentheses);
	    	stack.pop();
	    	// push ")"
	    	if (!stack.empty() && stack.peek()=="(") {
	    		stack.pop();
	    		dfs(stack, parentheses+")", nParentheses);
	    		stack.push("(");
	    	}
	    }
}