Can anyone help me with this problem??

I am trying to do a coding question, but i am not able to understand it.
Here is the question

Q. A cake factory makes various different varieties of cakes. It is the largest factory in the state and takes orders from different places to prepare and deliver cakes.
The cake factory has a very large number of employees but not all employees come for work everyday.
Due to this, some days the cake factory can make a large delivery while on other days, they may be able to deliver only a handful of cakes.

The factory produces M number of cakes each day and all cakes weigh differently.
Every morning, the manager gets an order to deliver N kgs of cake. The factory can either completely deliver the order or not deliver the order at all.
Help the manager of the cake factory to determine whether can be delivered for the day or not.

Note: The cakes produced by the factory have to be delivered as a whole; they cannot be cut into pieces.


  1. 1 <= T <= 1000

  2. 1 <= M <= 1000

  3. 1 <= weight of each cake <= 1000

  4. 1 <= N <= 10000

…Input Format
…First line contains T which indicates the number of days for which the delivery is to be made.

…Second line contains M + 1 space separated integers in which the first integer denotes the number of cakes
to be made in one day
and the following M integers denote the weight of each cake.

…Third line contains N which indicates the weight of cake in kgs which needs to delivered.

Output Format
…Output YES if the delivery for that day can be made, otherwise NO for each test case.

Sample Input 1
4 12 2 15 9


7 20 13 5 8 2 11 3


3 7 4 1


Sample Output 1


Sample Input 2
2 4 7

8 2 1 7 6 10 4 2 2


Sample Output 2


I am not able to get the problem. can somebody please tell me with this.

It is a problem of Dynamic programming.
For understanding the problem take example of
4 12 2 15 9
here 4 is number of cakes made and you have to make 11 by adding any numbers from array {12,2,15,9} that is 9+2 so answer is YES
let a[m]={a1,a2,a3,a4,a5,} is the array of weights of cakes. and n is weight to be delivered.
fuction to solve is:- sol{int a[],st,n} //st is 0 initially
now there are two possibilities
1.n will have a1
2. n will not have a1
now problem breaks in two sub-problems
1.making n by a[m]-{a1} that is sol{a[],1,n}
2.and making n-a[1] by a[m]={a1} that is sol{a[],1,n-a[1]}
use this approach.