| Time Limit | $5$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $23$ | 正确数量 | $16$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 | 递归 循环 |
Exhaustive Search
Write a program which reads a sequence A of n elements and an integer M, and outputs "yes" if you can make M by adding elements in A, otherwise "no". You can use an element only once.
You are given the sequence A and q questions where each question contains Mi.
5
1 5 7 10 21
8
2 4 17 8 22 21 100 35
no
no
yes
yes
yes
yes
no
no
n ≤ 20
q ≤ 200
1 ≤ elements in A ≤ 2000
1 ≤ Mi ≤ 2000
You can solve this problem by a Burte Force approach. Suppose solve(p, t) is a function which checkes whether you can make t by selecting elements after p-th element (inclusive). Then you can recursively call the following functions:
solve(0, M)
solve(1, M-{sum created from elements before 1st element})
solve(2, M-{sum created from elements before 2nd element})
...
The recursive function has two choices: you selected p-th element and not. So, you can check solve(p+1, t-A[p]) and solve(p+1, t) in solve(p, t) to check the all combinations.
For example, the following figure shows that 8 can be made by A[0] + A[2].
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$3 $ms] | 多喝热水 | 431650 | 2019-05-22 19:18:26 |
| 内存最少[$2020 $KB] | AOJ大管家 | 338593 | 2018-12-05 21:37:41 |
| 第一AC | AOJ大管家 | 328894 | 2018-11-25 07:13:05 |
| 第一挑战 | AOJ大管家 | 328892 | 2018-11-25 07:11:05 |
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|