java - 回溯递归问题来解决平衡括号

Question

我需要了解如何从递归函数回溯。我知道阶乘或斐波那契等基本函数是如何完成的。我不明白这个问题。

我尝试消除第二个递归调用中的其他条件，但它会生成所有可能的括号集，包括不平衡的括号集。

public final class Example {
    public static void parentheses(int left, int right, String str) {
        if (left == 0 && right == 0) {
            System.out.print(str);
            System.out.print(", ");
        }

        if (left > 0) {
            str += "(";
            parentheses(left - 1, right, str);
        }

        if (right > 0 && right > left) {
            str += ")";
            parentheses(left, right - 1, str);
        }
    }

    public static void main(String[] args) {
        parentheses(3, 3, "");
    }
}

我希望结果是所有可能的平衡括号集但是在每次递归调用之后我都会得到 1 个额外的左括号。预期输出是:

((())), (()()), (())(), ()(()), ()()(),

我得到的输出是:

((())), ((()()), ((()()(), (()(()), (()(()(),

Answer 1

问题出在下面。

 str += "(";

您每次都会创建一个新的字符串对象并在递归调用中传递它。因此，每个递归调用的字符串对象都有不同的值，因此您预期的递归会失败。 Java 中的字符串是不可变的。

将代码更改为以下内容:

        public static void parentheses(int left, int right, String str) {

        if ( right==0 && left==0) {
            System.out.print(str);
            System.out.print(", ");

        }
        if (left > 0) {
            parentheses(left-1, right, str +"(" ); // New object will be created but its value will be dereferenced from the old one and attached to the new one.
            // As a result all our manipulation of string we did will be saved.
        }
        if ( right >0 && right > left) {
            parentheses(left, right - 1, str +")" );
        }
    }

输入:

parentheses(3,3,""); // Function call

输出:

((())), (()()), (())(), ()(()), ()()(),