Help in MARCHA1

help
, , ,
1

Can someone help me with this one.

here is the link to my code.
https://www.codechef.com/viewsolution/16308609

2

Please also describe your approach, someone needs to understand your code in order to be able to help you.

3

So after reading the question, we know that you will get mugged "if there is a subset of your banknotes that sums to m ".

Link To Help

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

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