No submission language available for this problem.

题目描述

给出不同的几个数字，以及一个目标值

问最少可以用多少个数字相加得到该目标值

如果已有的数字，任意组合均无法与目标值相等, 那么输出 -1.

注意若本题用记忆化递归写法完成，可以起到很好的训练效果。

输入格式

第一行一个整数 $n$，表示会有 $n$ 个数字 $n \le 500$

第二行 $n$ 个正整数，每个数不超过 $100$

第三行一个整数 $x$ ($0 \leq x \leq 5*10^4$) 表示目标值。

输出格式

一个整数表示总数，若无法组合输出 $-1$

3
1 2 5
11

3

样例 1 解释

选择 5 5 1 即可

1
2
3

-1

样例 2 解释

无法用 2 凑出 3，因此 -1

2
1 9
0

0

样例 3 解释

只要不取任何数字，就能获得数字 0 目标