递归确定是否存在与给定的int参数匹配的正整数数组的子集和？

解决方案应该是递归的，零是任何集合中的一个元素，并且可以多次使用集合中的元素。递归确定是否存在与给定的int参数匹配的正整数数组的子集和？

例如，如果数组为{3,5,7}，则17将返回true，因为5 + 5 + 7 = 17 但4将返回false。

我已经试过这样：

public static boolean isSumOf(int [] s, int n) 
{ 
     return isSumOf(s, s.length, n); 
} 
static boolean isSumOf(int s[], int length, int n) 
{ 
    // Base Cases 
    if (n == 0) 
    { 
     return true; 
    } 

    if (length == 0 && n != 0) 
    { 
     return false; 
    } 

    // If last element is greater than sum, then ignore it 
    if (s[length-1] > n) 
    { 
     return isSumOf(s, length-1, n); 
    } 


    /* else, check if sum can be obtained by any of the following 
     (a) including the last element 
     (b) excluding the last element */ 
    return isSumOf(s, length-1, n) || isSumOf(s, length-1, n-s[length-1]); 
}

，但它排除了多次

来源

2017-06-14 rico bell

不要缩短阵列，步行穿过所有的值在循环这样的添加元素的能力：

//base cases 
... 
res = false; 
for(i=0; i<length; i++) 
    if (s[i]<= n) 
     res = res || isSumOf(s[], length, n - s[i]); 
return res;

如果不允许循环，则调用带有和不带最后一个元素的递归（注意我在第二个调用中删除了-1）：

return isSumOf(s, length-1, n) || isSumOf(s, length, n-s[length-1]);

来源

2017-06-14 07:46:08 MBo

我忘了说，我不允许使用循环，但它的一个有趣的方向... –

看到更新..... – MBo

哇，我不敢相信！我正在努力解决这个问题......非常感谢你！ –

试试这个。

static boolean isSumOf(int s[], int length, int n) { 
    if (n == 0) 
     return true; 
    if (length == 0) 
     return false; 
    int last = s[length - 1]; 
    if (last > n) 
     return isSumOf(s, length - 1, n); 
    return isSumOf(s, length - 1, n) 
     || isSumOf(s, length - 1, n - last) 
     || isSumOf(s, length, n - last); 
}

结果

int[] array = {3, 5, 7}; 
int length = array.length; 
System.out.println(isSumOf(array, length, 12)); // true 
System.out.println(isSumOf(array, length, 5)); // true 
System.out.println(isSumOf(array, length, 8)); // true 
System.out.println(isSumOf(array, length, 25)); // true 
System.out.println(isSumOf(array, length, 4)); // false

来源

2017-06-14 08:42:38 saka1029

@SanketMakani对不起，我改变了我的答案。 – saka1029

你的实现是更标准的子集和，和操作过程中是不允许的元素组成，其中所述重复的。

但是您的要求允许重复元素。

例如，如果数组是{3,5,7}，所以17将返回true，因为5 + 5 + 7 = 17但是4将返回false。

这就是为什么你没有得到结果。正如MBo在计算和计算中检查所有元素所指出的。

注：如果要求是要找到所有这样的组合那么它更像是一个coin exchange problem

希望它能帮助！

来源

2017-06-15 06:14:45 arunk2

递归确定是否存在与给定的int参数匹配的正整数数组的子集和？

回答

相关问题