Can someone help me with this one.
here is the link to my code.
https://www.codechef.com/viewsolution/16308609
Can someone help me with this one.
here is the link to my code.
https://www.codechef.com/viewsolution/16308609
So after reading the question, we know that you will get mugged "if there is a subset of your banknotes that sums to m ".
Let isSubSetSum(int set[], int n, int sum) be the function to find whether there is a subset of set[] with sum equal to sum. n is the number of elements in set[].
The isSubsetSum problem can be divided into two subproblems
(a) Include the last element, recur for n = n-1, sum = sum – set[n-1]
(b) Exclude the last element, recur for n = n-1.
#include <bits/stdc++.h>
using namespace std;
int arr[100];
bool isSubsetSum(int set[], int n, int sum) {
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]);
}
int main() {
int t;
cin >> t;
while (t--) {
int n, sum;
cin >> n >> sum;
for (int k = 0; k < n; k++) cin >> arr[k];
if (isSubsetSum(arr, n, sum))
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
TEST CASE:
1
15 5042
726
505
299
293
686
184
656
372
708
836
498
247
704
469
648
EXPECTED OUTPUT:
Yes
YOUR OUTPUT:
NO
Please also describe your approach, someone needs to understand your code in order to be able to help you.