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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#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次方）。。。
