C - 루프가없는 서브 세트 합계를 재귀 적으로 찾습니다.

Question

도움이 필요합니다. 이 코드는 sum까지 합쳐진 n 크기의 배열 set[]이 있는지 찾아내는 C 코드를 가지고 있습니다.

예 : 대한

n = 3; 
sum = 6; 

하지만 거짓 :

n = 1; 
sum = 4; 

정립-2 일부 {1,3} = 4 그것도와 사실 때문에

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

위의 코드가 true 반환

일부 경우에는 작동하지만 드라이버의 대소 문자가 반환되지 않습니다. 이 코드에서 드라이버에 대해 올바르게.

#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]); 
} 

Answer 1

집합의 크기와 하위 집합의 크기가 혼동 스럽습니다. 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; 
} 

Answer 2

또한 인수의 집합 크기를 전달해야합니다. 다음 코드가 작동합니다.

#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; 
} 

Answer 3

목록의 끝에있는 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; 
} 

음수에도 적용됩니다.