无法用二维数组缓存实现子集和Top-Down Memoization解法求助

看起来你在实现子集和的自顶向下记忆化解法时遇到了问题，我来帮你排查并修正代码。首先先看你提供的现有代码片段：

public static void main(String []args){
    int set[] = {3, 34, 4, 12, 5, 2};
    int sum = 9;
    int n = set.length;
    if (isSubsetSum(set, n, sum) == true)
        System.out.println("Found a subset with given sum");
    else
        System.out.println("No subset with given sum");
}
static boolean isSubsetSum(int set[], int n, int sum) {
    // 你的代码未完成，这是问题的核心所在
}

常见错误分析 #

你的代码大概率缺失了这几个关键部分：

• 没有创建合适的记忆化缓存，导致重复计算相同状态
• 递归终止条件不完整，无法正确处理边界情况
• 没有在递归中读取和写入缓存，失去了记忆化的意义

修正后的完整代码 #

下面是补全并优化后的代码，包含了记忆化缓存的正确使用：

public class SubsetSumMemoization {
    // 记忆化缓存：cache[n][sum] 记录前n个元素能否组成和为sum的子集
    // 用null标记未计算的状态，避免与布尔值的true/false混淆
    static Boolean[][] cache;

    public static void main(String []args){
        int set[] = {3, 34, 4, 12, 5, 2};
        int sum = 9;
        int n = set.length;
        
        // 初始化缓存：维度为(n+1)x(sum+1)，覆盖从0到n的元素数、0到sum的目标和
        cache = new Boolean[n+1][sum+1];
        
        if (isSubsetSum(set, n, sum))
            System.out.println("Found a subset with given sum");
        else
            System.out.println("No subset with given sum");
    }

    static boolean isSubsetSum(int set[], int n, int sum) {
        // 终止条件1：目标和为0，空子集即可满足，返回true
        if (sum == 0) {
            return true;
        }
        // 终止条件2：没有元素可选但目标和不为0，返回false
        if (n == 0 && sum != 0) {
            return false;
        }

        // 优先检查缓存：如果状态已计算，直接返回结果
        if (cache[n][sum] != null) {
            return cache[n][sum];
        }

        // 情况1：当前元素大于目标和，无法选择它，递归处理前n-1个元素
        if (set[n-1] > sum) {
            cache[n][sum] = isSubsetSum(set, n-1, sum);
            return cache[n][sum];
        }

        // 情况2：两种选择：选当前元素（目标和减去该元素）或不选，只要一种满足即可
        boolean include = isSubsetSum(set, n-1, sum - set[n-1]);
        boolean exclude = isSubsetSum(set, n-1, sum);
        cache[n][sum] = include || exclude;
        return cache[n][sum];
    }
}

关键逻辑说明 #

• 缓存设计：使用Boolean类型数组而非boolean，是因为可以用null明确标记未计算的状态，避免默认值false干扰判断
• 记忆化核心：每次递归前先检查缓存，若已有结果直接复用，彻底避免重复计算相同的(n, sum)状态
• 递归分支：覆盖了所有可能的选择（选或不选当前元素），确保不会遗漏可行的子集组合

测试这段代码，你的输入set = {3,34,4,12,5,2}和sum=9会输出Found a subset with given sum（比如子集{4,5}或{3,4,2}都能满足要求）。

内容的提问来源于stack exchange，提问作者Oomph Fortuity