了解生成括号的函数

algorithm java

2022-09-03 16:45:48

我有这个算法来生成格式良好的括号的所有组合。

有人可以解释算法的核心概念吗？我试图通过它进行调试，但我似乎仍然无法掌握算法背后的基本概念。

此外，关于如何为这个问题提出这样的算法的任何一般建议，即一个人如何变得如此聪明地以这种方式解决它，或者必须做些什么练习才能达到这个阶段。

问题：

给定一对括号，编写一个函数来生成格式正确的括号的所有组合。例如，给定，一个解集是：nn = 3
“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

法典：

public ArrayList<String> generateParenthesis(int n) {
    ArrayList<String> solutions = new ArrayList<String>();
    recursion(n, new String(), solutions);
    return solutions;
}

private void recursion(int n, String str, ArrayList<String> sol) {
    if(str.length() == 2 * n)
        sol.add(str);
    else {
        int left = 0;
        int right = 0;
        for(int i = 0; i < str.length(); ++i) {
            if(str.charAt(i) == '(')
                left++;
            if(str.charAt(i) == ')')
                right++;
        }
        if(left == right)
            recursion(n, str + "(", sol);
        else if(right < left) {
            if(left < n)
                recursion(n, str + "(", sol);
            recursion(n, str + ")", sol);
        }
    }
}

答案 1

它帮助我直观地看到调用是如何堆叠的。我在呼叫中添加了一个参数，并在每次呼叫上打印出来，为新呼叫的每个深度参数添加四个空格。这为我们提供了调用顺序的良好视图。String depthdepth + str

这是它的代码：

recursion(3, new String(), solutions, "");
//...
private static void recursion(int n, String str, ArrayList<String> sol, String depth) {
    System.out.println(depth + str);
    //...
        if(left == right)
            recursion(n, str + "(", sol, depth + "    ");
        else if(right < left) {
            if(left < n)
                recursion(n, str + "(", sol, depth + "    ");
            recursion(n, str + ")", sol, depth + "    ");
}

这是它打印出来的内容：

(
    ((
        (((
            ((()
                ((())
                    ((()))
        (()
            (()(
                (()()
                    (()())
            (())
                (())(
                    (())()
    ()
        ()(
            ()((
                ()(()
                    ()(())
            ()()
                ()()(
                    ()()()

每个递归级别都会向输出添加另一个缩进。如果两个输出处于相同的缩进级别，则它们都是从相同的递归级别调用的。

这是另一个视觉对象：

请注意，每个节点都是更深层次的递归，每次子节点直接从父节点下来时，它都不会拆分为两个递归路径。也就是说，父节点只调用一次。recursion

Colorful parentheses

答案 2

递归肯定会弄乱你的头。这是另一种可能更容易遵循的方法：

void generate() {
    ArrayList<String> results = new ArrayList<String>();
    generateParentheses(4, 0, new StringBuilder(), results);
    System.out.println(results);
}

void generateParentheses(final int remaining, final int openCount, final StringBuilder s, final List<String> results) {
    if (remaining == 0 && openCount == 0) {
        results.add(s.toString());
        return;
    }
    if (openCount > 0) { // we can close the open one
        s.append(")");
        generateParentheses(remaining, openCount-1, s, results);
        s.setLength(s.length()-1); // pop the last char off
    }
    if (remaining > 0) { // start a new one
        s.append("(");
        generateParentheses(remaining-1, openCount+1, s, results);
        s.setLength(s.length()-1); // pop the last char off
    }
}

输出为[()()()(), ()()(()), ()(())(), ()(()()), ()((())), (())()(), (())(()), (()())(), (()()()), (()(())), ((()))(), ((())()), ((()())), (((())))]

这从另一端解决问题。你是怎么想出这些模式的？

从对数（）开始。remaining

只有两种可能性：开放或封闭。只有当有一些剩余的要追加时，才能追加左括号。仅当有相应的要关闭的左括号时，才能追加右括号。

所以你只需要数一下你还剩下多少，以及你有多少括号。让递归处理其余部分。