了解函数以生成括号

Question

我有这个算法来生成格式正确的括号的所有组合.

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

另外,关于如何为这个问题提出这样一个算法的任何一般性建议,即如何通过这种方式如此聪明地解决它,或者为了达到这个阶段必须做什么练习.

问题:

给定n括号对,编写一个函数来生成格式正确的括号的所有组合.例如,给定n = 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);
        }
    }
}

Answer 1

它可以帮助我直观地看到呼叫是如何堆叠的.我String depth在调用中添加了一个参数,并depth + 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一次.

Answer 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)开始.

只有两种可能性:开放或封闭.如果还有一些要追加,则只能附加一个空括号.如果要关闭相应的左括号,则只能附加近括号.

因此,您只需要计算剩余的剩余数量,以及您对括号的深入程度.让递归处理剩下的事情.