以递归方式找到子集总和的错误java

n是一个子集，它包含所需的总和（目标）大小：所以

set[] = {5,6,9,-1,4,2} 
n = 3 
sum = 10

将等同于真实的，因为大小为3，总结的子集10是{9} -1,2-

public static boolean isSubsetSum(int[] set, int n, int sum) { 
int[] copy = new int[set.length - 1]; 
System.arraycopy(set, 0, copy, 0, set.length - 1); 

// Base Cases 
    if (sum == 0 && n == 0) 
    return true; 
    if (set.length == 0)  // fixed base case. 
    return false; 

    if (set[set.length - 1] > sum) { 
    return isSubsetSum(copy, n, sum); 
    } 

    return isSubsetSum(copy, n, sum) || isSubsetSum(copy, n-1, sum - set[set.length-1]); 
}

来源

2014-03-06 user3362954

我觉得你的主要问题是，当你调用

return isSubsetSum(copy, n, sum)

n和sum不会减少，所以它们永远不会达到零。在n和sum被更改的末尾确实有呼叫，但通过阅读代码可以清楚地看出，对于某些功能输入，您永远不会到达那里。

来源

2014-03-06 23:33:24 hlovdal

我已经经历了与子集{-4,0,4}，n = 2（或3），总和需要为0 ...任何建议？ – user3362954

您看到的递归错误（至少部分）是因为您的return语句的左侧。

copy是一组确切的副本，所以调用isSubsetSum(copy, n, sum)与调用isSubsetSum(set, n, sum)相同。如果其中一个基本案例不适用于设置，则它也不适用于复制，导致||评估的左半部分（其首先评估）的无限递归。因此，程序永远不会找到问题的解决方案，并且最终你会希望看到递归错误（或者它将永远保持持续不断！）

为了避免这种情况，您需要修改递归调用在return语句中只处理问题的一个子集。

来源

2014-03-06 23:33:44 emerssso

哪个返回语句？你会如何推荐递减？ – user3362954

我指的是最后的return语句：'return isSubsetSum（copy，n，sum）|| isSubsetSum（copy，n-1，sum-set [set.length-1]）;'。 – emerssso

调试你的代码后，我看到你得到这个错误：java.lang.NegativeArraySizeException，你得到的是因为当你的数组大小为0时，你尝试在你的方法的第二行复制它的长度为-1。
更改线条的顺序（在开始处检查此基本情况），并且您的方法将正常工作。

来源

2014-03-06 23:42:09

以递归方式找到子集总和的错误java

回答

相关问题