Go java 算法之括号生成示例详解

算法介绍

本算法是使用回溯算法来实现的，先在左边放置一个'('，再将')'放置在之前的'('后面。在任意时刻，使用的左括号数量都不应超过 n，也就是原本需要生成的数量。

代码实现

public List<String> generateParenthesis(int n) {

    List<String> result = new ArrayList<String>();

    if(n == 0) {
        return result;
    }

    String str = "";
    // 回溯
    backtrack(result, str, 0, 0, n);

    return result;
}

public void backtrack(
        List<String> result,
        String str,
        int open,
        int close,
        int n
){
    if(str.length() == 2*n) { // 生成完n个括号
        result.add(str);
        return;
    }

    // 左括号数量不能超过限制
    if(open<n) {
        backtrack(result, str + '(', open+1, close, n);
    }

    // 如果还有剩余的右括号未使用
    if(close<open) {
        backtrack(result, str + ')', open, close+1, n);
    }

}

示例说明

示例1：

生成括号对数为3个，运行结果如下：

List<String> list = generateParenthesis(3);
System.out.println(list);

输出结果：

["((()))", "(()())", "(())()", "()(())", "()()()"]

示例2：

生成括号对数为4个，运行结果如下：

List<String> list = generateParenthesis(4);
System.out.println(list);

输出结果：

["(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()"]

以上就是本算法的详细攻略，希望能对您有所帮助。