Problem 2663 --Recursion / Divide and Conquer - Exhaustive Search

2663: Recursion / Divide and Conquer - Exhaustive Search

"
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.

In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers (Mi) are given.
For each question Mi, print yes or no.
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].



推荐代码 查看2663 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$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

赛题来源/所属竞赛 会津大学《挑战数据结构与算法》 挑战数据结构与算法

竞赛编号 竞赛名称 竞赛时间 访问比赛