C - 遞歸找到沒有循環的子集總和

我期待得到一些幫助。我在c代碼中找到了這個代碼，該代碼的作用是查找是否存在大小爲n的數組set[]的一個子集，它加起來爲sum。C - 遞歸找到沒有循環的子集總和

實施例：

set[] = {1,2,3}; 
n = 2; 
sum = 4;

上面的代碼將返回true，因爲尺寸-2子集{1,3} = 4 它也將與真：

n = 3; 
sum = 6;

但假爲：

n = 1; 
sum = 4;

它適用於某些情況，但驅動程序中的情況不會返回在此代碼中適當地爲驅動程序。請注意，我不能改變的參數和不希望使用任何種類的循環

和代碼是在這裏：

#include <stdio.h> 

bool isSubsetSum(int set[], int n, int sum) 
{ 
    // Base Cases 
    if (sum == 0) 
     return true; 
    if (n == 0 && sum != 0) 
     return false; 

    if (set[n-1] > sum) 
     return isSubsetSum(set, n-1, sum); 

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

// Driver program to test above function 
int main() 
{ 
    int set[] = {6,5,6}; 
    int sum = 12; 
    int n = 2; 
    if (isSubsetSum(set, n, sum) == true) 
     printf("Found a subset with given sum"); 
    else 
     printf("No subset with given sum"); 
    return 0; 
}

JAVA適應：（錯誤太）n是子集的大小

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

您能更加明確地瞭解驅動程序的失敗情況嗎？ – Coconop

任何循環都可以通過遞歸進行編程（只要您有足夠深的堆棧或尾部呼叫優化）。謝謝lambda微積分。 – pat

@Michelle你會錯的。所有可以使用循環完成的事情也可以使用遞歸完成。此外，除了循環之外，子集和還需要額外的DS來計算。（矩陣如果使用DP，或者一堆模仿蠻力的遞歸） – amit

您正在混淆集合的大小和子集的大小。設n設計全套大小和k子集的大小。然後：

#include <stdio.h> 
bool isSubsetSum(int set[], int n, int k, int sum) 
{ 
    // Base Cases 
    if (sum == 0 && k == 0) 
    return true; 
    if (n == 0)  // fixed base case. 
    return false; 

    if (set[n-1] > sum) 
    return isSubsetSum(set, n-1, k, sum); 

    return isSubsetSum(set, n-1, k, sum) || isSubsetSum(set, n-1, k-1, sum-set[n-1]); 
} 

int main() 
{ 
    int set[] = {6,5,6}; 
    int sum = 12; 
    int n = 3; 
    int k = 2; 
    if (isSubsetSum(set, n, k, sum)) 
    printf("Found a subset with given sum\n"); 
    else 
    printf("No subset with given sum\n"); 
    return 0; 
}

來源

2014-03-06 16:28:00 hivert

我把這個問題看作含義'n'是子集的大小，而不是原始集合。（特別是基於示例。） – Michelle

不完全正確。在某些情況下，Seg錯誤。 –

非常感謝您的報告。真的！如果固定基本情況。 – hivert

您還需要傳遞該參數的大小。以下代碼有效。

#include <stdio.h> 

bool isSubsetSum(int set[], int m,int n, int sum) 
{ 

if (n == 0 && sum == 0) 
return true; 
if(m==0) 
    return false; 

if (set[m-1] > sum) 
return isSubsetSum(set, m-1,n, sum); 

return isSubsetSum(set, m-1,n, sum) || isSubsetSum(set, m-1,n-1, sum-set[m-1]); 
} 

// Driver program to test above function 
int main() 
{ 
int set[] = {6,5,6}; 
int sum = 13; 
int n = 2; 
if (isSubsetSum(set, 3,n, sum) == true) 
printf("Found a subset with given sum"); 
else 
printf("No subset with given sum"); 
return 0; 
}

來源

2014-03-06 16:33:37

無論如何不改變參數？ – user3362954

isSubsetSum不會對set的大小有任何想法，如果它沒有從調用函數傳遞。所以你必須修改參數。 –

在列表末尾使用0來指示設定的長度。

#include <stdio.h> 
#include <stdbool.h> 

bool isSubsetSum(int set[], int n, int sum) { 
    if (n == 0) 
    return sum == 0; 
    if (set[0] == 0) // End of the line 
    return false; 
    if (isSubsetSum(set + 1, n, sum)) // Do not use first element 
    return true; 
    if (isSubsetSum(set + 1, n - 1, sum - set[0])) // Use first element 
    return true; 
    return false; 
} 

// Driver program to test above function 
int main() { 
    int set[] = { 6, 5, 6, 0 }; 
    int sum = 12; 
    int n = 2; 
    if (isSubsetSum(set, n, sum) == true) 
    printf("Found a subset with given sum"); 
    else 
    printf("No subset with given sum"); 
    return 0; 
}

這也適用於負數。

來源

2014-03-06 18:15:59 chux

C - 遞歸找到沒有循環的子集總和

回答

相關問題