题解 | #括号生成#

思路
这道题就是在不停选括号，要么选左括号，要么选右括号。
并且，是有约束地选：

只要(有剩，就可以选(。 (((((这么选，都还不能判定为非法。
当剩下的)比(多时，才可以选)，否则，)不能选，选了就非法了（结合下图感受一下）。
下图描述节点的状态有：当前构建的字符串、左 右括号所剩的数量。

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {

        if (n == 0) {
            return new ArrayList<String>();
        }

        ArrayList<String> list = new ArrayList<String>();
        backTrace("", 0, 0, n, list);
        return list;
    }

    public void backTrace (String currentStr, int leftNum, int rightNum, int n, ArrayList<String> list) {

        if (2 * n == currentStr.length()) {
            list.add(currentStr);
            return;
        }

        //如果左括号的数量 < n 因为下标是从0开始的 所以不能=n
        if (leftNum < n) {
            backTrace(currentStr + "(", leftNum+1, rightNum, n, list);
        }

        //如果右括号的数量 < leftNum 左括号的数量因为下标是从0开始的 所以不能=leftNum
        if (rightNum < leftNum) {
            backTrace(currentStr + ")", leftNum, rightNum+1, n, list);
        }
    }
}