Hello coders, today we are going to solve Paying Up CodeChef Solution whose Problem Code is MARCHA1.
Task
In the mysterious country of Byteland, everything is quite different from what you’d normally expect. In most places, if you were approached by two mobsters in a dark alley, they would probably tell you to give them all the money that you have. If you refused, or didn’t have any – they might even beat you up.
In Byteland the government decided that even the slightest chance of someone getting injured has to be ruled out. So, they introduced a strict policy. When a mobster approaches you in a dark alley, he asks you for a specific amount of money. You are obliged to show him all the money that you have, but you only need to pay up if he can find a subset of your banknotes whose total value matches his demand. Since banknotes in Byteland can have any positive integer value smaller than one thousand you are quite likely to get off without paying.
Both the citizens and the gangsters of Byteland have very positive feelings about the system. No one ever gets hurt, the gangsters don’t lose their jobs, and there are quite a few rules that minimize that probability of getting mugged (the first one is: don’t go into dark alleys – and this one is said to work in other places also).
Input Format
The first line contains integer t, the number of test cases (about 100). Then t test cases follow. Each test case starts with n, the number of banknotes in your wallet, and m, the amount of money the muggers asked of you. Then n numbers follow, representing values of your banknotes. Your wallet does not hold more than 20 banknotes, and the value of a single banknote is never more than 1000.
Output Format
For each test case output a single line with the word ‘Yes’ if there is a subset of your banknotes that sums to m, and ‘No’ otherwise.
Example
Sample Input
5
3 3
1
1
1
5 11
1
2
4
8
16
5 23
1
2
4
8
16
5 13
1
5
5
10
10
20 132
17
6
4
998
254
137
259
153
154
3
28
19
123
542
857
23
687
35
99
999
Sample Output
Yes
Yes
Yes
No
Yes
Explanation
For example, in the last case you have to pay up, since: 6+3+123=132.
Solution – Paying Up
C++
#include<iostream> using namespace std; bool answer(int mon,int ar[20],int len){ for(int end=len;end>=0;end--){ int temp; temp=mon-ar[end]; if(temp==0){ return true; } for(int j=0;j<end;j++){ if(ar[j]==temp){ return true; } } if(answer(temp,ar,end-1)==true){ return true; } } return false; } int main(){ int t; cin>>t; while(t--){ int n,m; cin>>n>>m; int arr[n]; for(int i=0;i<n;i++){ cin>>arr[i]; } bool ans=answer(m,arr,n-1); if(ans){ cout<<"Yes"<<endl; } else{ cout<<"No"<<endl; } } return 0; }
Python
# cook your dish here import itertools t = int(input()) for i in range(t): n,m = map(int, input().split()) ans = [] comb = [] flag = 0 for j in range(n): k = int(input()) if k<=m: ans.append(k) for g in range(len(ans)+1): comb_obj = itertools.combinations(ans,g) comb += list(comb_obj) for g in comb: if sum(g)==m: flag = 1 if flag == 1: print("Yes") else: print("No")
Java
/* package codechef; // don't place package name! */ import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class Codechef { public static void main (String[] args) throws java.lang.Exception { Scanner scn = new Scanner(System.in); int i = scn.nextInt(); while (i-- > 0) { int n = scn.nextInt(); // my wallet int m = scn.nextInt(); // amount of money the muggers want int[] w = new int[n+1]; for (int j = 0; j < n; j++) { w[j] = scn.nextInt(); } w[n] = 0; System.out.println(calc(n, m, w)); } } public static String calc(int n, int m, int[] w) { Arrays.sort(w); boolean[][] tab = new boolean[n+1][m+1]; tab[0][0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { if (w[i] > j) { tab[i][j] = tab[i-1][j]; continue; } if (tab[i - 1][j] || tab[i - 1][(j - w[i])]) tab[i][j] = true; } } if (tab[n][m]) return "Yes"; else return "No"; } }
Disclaimer: The above Problem (Paying Up) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.