#6673. 目标和是否存在
-
ID: 6673
传统题
1000ms
256MiB
尝试: 10
已通过: 5
难度: 9
上传者:
hantianliang
标签> 目标和是否存在
题面：目标和是否存在
时间限制： 1 秒 内存限制： 256 MB
给定 n 个正整数 a1, a2, ..., an，以及一个目标值 T。
你可以从这 n 个数中选择任意多个数，也可以一个都不选。
请判断是否存在一种选择方案，使得被选中的所有数之和恰好等于 T。
输入格式
第一行包含两个整数 n, T。
第二行包含 n 个正整数 a1, a2, ..., an。
输出格式
如果存在一种选择方案，使得所选数字之和恰好等于 T，输出：
YES
否则输出：
NO
数据范围
1 <= n <= 20
0 <= T <= 10^9
1 <= ai <= 10^9
样例
输入
3 7
2 3 5
输出
YES
说明
可以选择数字 2 和 5，它们的和为 7，恰好等于目标值。
测试点说明表
| 测试点编号 | n ≤ | T ≤ | 特殊性质 | 设计目的 |
|---|---|---|---|---|
| 1 | 1 | 0 | 目标为 0 |
覆盖空集即可满足目标的边界 |
| 2 | 5 | 单个数恰好等于目标 | 覆盖最小非空可行情况 | |
| 3 | 3 | 7 | 样例数据 | 对应原程序固定数据，答案为 YES |
| 4 | 1 | 目标小于所有元素 | 检查超过目标剪枝与 NO 输出 |
|
| 5 | 4 | 10 | 全部选择恰好达到目标 | 覆盖选择多个数的可行情况 |
| 6 | 5 | 11 | 全部为偶数，目标为奇数 | 覆盖明显不可达情况 |
| 7 | 6 | 15 | 所有元素相同 | 检查重复元素下的子集选择 |
| 8 | 31 | 元素为 2 的幂 | 覆盖唯一组合结构 | |
| 9 | 10 | 29 | 全部为偶数，目标为奇数 | 覆盖中等规模 NO 数据 |
| 10 | 20 | 100 | 极限 n，全部为奇数 |
覆盖较大规模和深层搜索 |