遞歸確定是否存在與給定的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參數匹配的正整數數組的子集和？

回答

相關問題