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
#include<iostream>
using namespace std;
int A[25];
int n;
int solve(int i ,int tmp) {
if (tmp == 0)
return 1;
if (i >= n)
return false;
int res = solve(i + 1, tmp) || solve(i + 1, tmp - A[i]);
//针对于A[i]，有选或者不选的权力这样一直递归下去，当tmp=0时候，返回真
return res;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> A[i];
int t; cin >> t;
while (t--) {
int tmp; cin >> tmp;
if (solve(0, tmp))
cout << "yes" << endl;
else
cout << "no" << endl;
}
}Summary
递归函数中重复调用了两个递归函数，算法复杂度为0（2的n次方）。。。
废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：Exhaustive Search
