CODEM5 - Problem5


You are given an array of weights of n objects and your task is to select minimum number of objects whose sum of weights is exactly equals to some given k.

Input

Line 1 - number of test cases T (<= 10) followed by 2 lines for each test case
Line 2 - Number of objects n (<= 20) and total weight k (<= 10^4)
Line 3 - weights (<= 10^4) of n objects (each separated by space)

Output

Minimum number of objects whose weights sums to k.

Example

Input:
2
5 9
10 9 4 3 5
3 7
1 2 3 Output: 1
impossible

Explanation

For the first case the two combinations are possible: (9), (4, 5) hence minimum number of objects is 1.

For the second case there are no combinations possible hence impossible.


hide comments
asifalim: 2021-04-27 11:56:16

after(6) keeping a visited array got accepted!
Alhamdulillah
Hints: minimum coins change DP

scolar_fuad: 2019-10-12 19:44:42

knapsake in enough to solve this problem ...


take N=101 because information is wrong

subhikhalifeh: 2019-05-04 00:43:44

D:
(:
):
<(--)>

Last edit: 2019-05-04 00:45:27
kaneki0530: 2018-06-06 11:10:31

Backtracking!!! AC in one go

thanos_tapras: 2018-04-27 12:47:27

Tried with subset sum, but always WA. Tried again with bitmasks and got AC

prince_batra: 2018-03-24 18:57:50

I try this problem Just like subset sum problem of DP with minimum coins to form the sum but still getting WA?
Any corner case

chetan4060: 2017-12-08 19:51:20

try bitmask if rte
No dp

mahilewets: 2017-09-09 15:33:50

Knapsack

pradeep_yadav: 2017-08-26 15:44:33

Take n about 105

kshubham02: 2017-08-23 09:28:51

Buggy question, take n=100.


Added by:Bhavik
Date:2014-02-04
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem(for CODE MARATHON)