题解 | #括号生成#

import java.util.*;

public class Solution { /** * * @param n int整型 * @return string字符串ArrayList */ public ArrayList 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);
    }
}

}