平衡括号(一)——判断平衡括号

LeetCode_22_GenerateParentheses

题目分析：

首先什么是平衡括号--就是只有括号，而且"括得合法"的字符串。
题目让我们生成平衡括号，这里巧法就是，利用平衡括号的一个重要特点。
平衡括号，从"第一个字符开始"的"所有子串"，满足"("个数大于等于")"个数。
可观察n=3的所有平衡括号
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

解法：

public static List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<String>();
    helper(n, n, "", res);
    return res;
}

/**
 * 从0开始的任何子串 left个数>=right个数 既是合法串
 */
public static void helper(int left, int right, String out, List<String> res) {
    if (left < 0 || right < 0 || left > right) return;
    if (0 == left && 0 == right) {
        res.add(out);
        return;
    }
    helper(left - 1, right, out + "(", res);
    helper(left, right - 1, out + ")", res);
}