I was invited to give the test and the following question was asked.

There is a weighing scale and we have an array X of integers which represents weights we are having with us. We can measure all weights which can be formed by various combinations of these weights. Suppose array is {7,9,28} then we can measure 7,9,28,2,19,16, etc. Now we are given a range [A,B], we need to tell if we can measure all weights in the range. If we can’t measure all weights in range [A,B] then we can use one extra weight which is not in the given array. Lets call it W. If there are more than one W which can be used, select the one with lowest weight.

Input : First line no of Test Cases (Less than or equal to 10)

Every test case is as follows:

First Line contains N i.e. no of given weights (N<=30)

Next line contains array X (All weights are in the range 1 to 500)

Next Line contains two space separated integers A and B (1<=A<=B<=10000 or 20000 don’t remember exactly)

Also the weight W is from range 1 to 500.

Output :

Print YES if we can measure all the weights in the range. Print the lowest W in next line.

OR

If we can’t measure all the weights in the range print NO

For some cases constraints were somewhat smaller like N<=20, range [A,B] was lesser, etc.

I thought of trying meet in the middle and generate all possible sums and differences but for N=30 I don’t know will it work.

Help Please