java - 如何使用自下而上递归构建 n=3 的情况？

Question

我正在解决 Cracking the Coding Interview 中的问题，问题 9.6 第 110 页。

问题来了:
实现一个算法来打印所有有效的(例如，正确打开和关闭的 n 对括号的组合。示例
b(1) - “()”
b(2) - “(()), ()()”
b(3) - “((())), (()()), (())(), ()(()), ()()()”
我正在尝试使用作者在第 107 页讨论的自下而上的递归方法 - “我们从知道如何解决一个简单案例的问题开始，比如只有一个元素的列表，然后找出如何解决问题两个元素，然后是三个元素，依此类推。这里的关键是考虑如何针对前一个案例构建一个案例的解决方案”

这是我目前的代码

static void print(int n) {
    print(n, new HashSet<String>(), "", "");
}

static void print(int n, Set<String> combs, String start, String  end) {
    if(n == 0) {
        if(!combs.contains(start + end)) {
            System.out.print(start + end);
            combs.add(start + end);
        }
    } else {
        print(n-1, combs, "(" + start, end +")");
        System.out.print(", ");
        print(n-1, combs, start, end + "()");
        System.out.print(", ");
        print(n-1, combs, "()" + start, end);
    }
}

为了得到这段代码，我从第一种情况一直工作到第二种情况。我看到
b(2) = "(b(1)), b(1),b(1)"此代码适用于前两种情况。不过，我真的在为第三种情况而苦苦挣扎。有人可以给我一个提示(不是完整的答案，可以翻到书的背面)，关于如何从案例 2 转到案例 3，或者换句话说，如何使用案例 2 到达案例 3？比如你会如何从 (()), ()() 到
((())), (()()), (())(), ()(()), () ()()?你会放弃从 b(1) 到 b(2) 看到的模式，因为它对 b(2) 到 b(3) 不起作用吗？

Answer 1

我们可以使用这个递归公式从 b(n) 生成到 b(n + 1):

• (b(n - x))b(x) 和 0 <= x <= n

因此，您可以通过遍历所有 x 来获得所有组合。

代码:

public static ArrayList<String> cal(int num){

    if(num == 0){
        ArrayList<String> list = new ArrayList();
        list.add("");
        return list;
    }else{
        ArrayList<String>result = new ArrayList();
        for(int i = 0; i <= num - 1; i++){
            ArrayList<String> a = cal(i);
            ArrayList<String> b = cal(num - 1 - i);
            for(String x : a){
                for(String y : b){
                    result.add("(" + x + ")" + y);
                }
            }
        }
        return result;
    }
}

输入:3输出:()()(), ()(()), (())(), (()()), ((()))

输入:4输出:()()()(), ()()(()), ()(())(), ()(()()), ()((())), (())()(), (())(()), (()())(), ((()))(), (()()()), (()(( ))), ((())()), ((()())), (((())))