Exhaustive Search

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