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

Question

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

问题是：
实现一个算法来打印所有有效的（例如，正确打开和关闭的 n 对括号的组合。示例
b(1) - “()”
b(2) - “(()), ()()”
b(3) - “((())), (()()), (())(), ()(()), ()()()”
我正在尝试使用作者在第 107 页讨论的自下而上递归方法 - "We start with knowing how to solve the problem for a simple case, like a list with only one element, and figure out how to solve the problem for two elements, then for three elements, and so on. The key here is to think about how you can build the solution for one case off the previous case"

这是我目前的代码

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

感谢 Khanna111 指出我在原始答案中所犯的错误，该错误不完整并且对字符串模式的计数不足。因此，我相应地更新了我的答案。

请考虑感谢 Pham Trung 的正确递归公式回答。我的回答与他的基本相同，只是我从较小的子问题构建模式的方式略有不同（因为我发现在我的方法中更容易解释细节）。

============================================= ===========================

更新解决方案

对于大小为 n 的任何有效模式 s，s 恰好属于以下情况之一：

情况 1：s不能被分割成两个更小的有效模式
情况 2：s 可以分成两个有效的更小尺寸的模式

对于情况 1，s 必须采用 (_____) 形式，其中 _____ 是大小为 n - 1 的有效模式。因此，在这种情况下，对于大小为 n - 1 的每个有效模式 t，我们只需将 t 与 ( 和 [=25= 连接起来即可构造一个模式 s ] 分别作为前缀和后缀（即 s = (t)）。

对于情况 2，我们可以将 s 划分为 uv，其中 u 和 v 都是较小尺寸的有效模式。在这种情况下，我们必须考虑 u 和 v 的所有可能模式，其中 u 可以是大小为 i = 1, 2, ..., n - 1 的任何有效模式，而 v 可以是大小为 n - i.

的任何有效模式

当 n = 0 时，显然只有空字符串是有效模式，因此我们将 dp(0) = { "" } 作为我们的基本情况。下面给出了使用缓存来提高性能的完整实现：

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class BalancingBrackets {

    private static Map<Integer, Set<String>> dp = new HashMap<>();

    public static void main(String[] args) {
        Set<String> result = compute(4);

        boolean isFirst = true;
        for (String s : result) {
            if (isFirst) {
                isFirst = false;
                System.out.print(s);
            } else {
                System.out.print(", " + s);
            }
        }
    }

    private static Set<String> compute(Integer n) {
        // Return the cached result if available
        if (dp.containsKey(n)) {
            return dp.get(n);
        }

        Set<String> set = new HashSet<>();

        if (n == 0) {
            // This is the base case with n = 0, which consists only of the
            // empty string
            set.add("");
        } else if (n > 0) {
            // For generating patterns in case 1
            for (String s : compute(n - 1)) {
                set.add("(" + s + ")");
            }

            // For generating patterns in case 2
            for (int i = 1; i < n; i++) {
                Set<String> leftPatterns = compute(i);
                Set<String> rightPatterns = compute(n - i);

                for (String l : leftPatterns) {
                    for (String r : rightPatterns) {
                        set.add(l + r);
                    }
                }
            }
        } else {
            // Input cannot be negative
            throw new IllegalArgumentException("Input cannot be negative.");
        }

        // Cache the solution to save time for computing large size problems
        dp.put(n, set);

        return set;
    }

}

Answer 2

我们可以使用这个递归公式从 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 输出：()()()(), ()()(()), ()(())(), ()(()()), ()((())), (())()(), (())(()), (()())(), ((()))(), (()()()), (()(())), ((())()), ((()())), (((())))

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

How to build the case for n=3 using bottom up recursion?

java

algorithm

recursion

dynamic-programming

bottom-up