• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

Exhaustive Search

AOJ 站点默认 6个月前 (04-11) 169次浏览 已收录 0个评论
文章目录[隐藏]

Question

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.

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

Output
For each question Mi, print yes or no.

Constraints
n ≤ 20
q ≤ 200
1 ≤ elements in A ≤ 2000
1 ≤ Mi ≤ 2000
Sample Input 1
5
1 5 7 10 21
8
2 4 17 8 22 21 100 35
Sample Output 1
no
no
yes
yes
yes
yes
no
no

Meaning


从数组A中需拿出任意几个元素相加判断是否能得到给定的值Mi,如果可以输出yes,否则输出no

Sloution

首先,题目中的值n很小,那就直接递归给所有值全部列出来吧,也只是2的n次方。

Coding

Summary


递归函数中重复调用了两个递归函数,算法复杂度为0(2的n次方)。。。

个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:Exhaustive Search
喜欢 (0)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到