gs gs122 Checksum Complexity Classes and NP-Complete Problems - Subset Sum Problem - Quiz No.1

 #include <stdio.h> bool func(int arr[], int n, int sum) { if (sum == 0) return true; if (n == 0 && sum != 0) return false; if (arr[n-1] > sum) return func(arr, n-1, sum);  return func(arr, n-1, sum) || func(arr, n-1, sum-arr[n-1]); } int main() { int arr[] = {4,6, 12, 2}; int sum = 12; int n = sizeof(arr)/sizeof(arr[0]); if (func(arr, n, sum) == true) printf("true"); else printf("false"); return 0; } 

 #include <stdio.h> bool func(int arr[], int n, int sum) { bool subarr[n+1][sum+1]; for (int i = 0; i <= n; i++) subarr[i][0] = true; for (int i = 1; i <= sum; i++) subarr[0][i] = false; for (int i = 1; i <= n; i++) { for (int j = 1; j <= sum; j++) { if(j<arr[i-1]) subarr[i][j] = subarr[i-1][j]; if (j >= arr[i-1]) subarr[i][j] = subarr[i-1][j] || subarr[i - 1][j-arr[i-1]]; } } return subarr[n][sum]; }  int main() { int arr[] = {3, 3, 4, 4, 7}; int sum = 5; int n = sizeof(arr)/sizeof(arr[0]); if (func(arr, n, sum) == true) printf("true"); else printf("false"); return 0; } 

 #include <stdio.h> bool func(int arr[], int n, int sum) { if (sum == 0) return true; if (n == 0 && sum != 0) return false; if (arr[n-1] > sum) return func(arr, n-1, sum); return func(arr, n-1, sum) || func(arr, n-1, sum-arr[n-1]); } int main() { int arr[] = {4,6, 12, 2}; int sum = 12; int n = sizeof(arr)/sizeof(arr[0]); if (func(arr, n, sum) == true) printf("true"); else printf("false"); return 0; }