用递归和循环两种方法解决华为4月20日机试第一题(100分)

题目：

方法一：dfs暴力搜索

#include <iostream>
using namespace std;
#include <vector>

int cnt = 0;
int sum = 0;
vector<int> nums = 
{ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8 };
void dfs(int target, int err, int index) {
	if (err >= 3) return;
	if (sum == target) {
		cnt++;
		return;
	}
	if (sum > target) {
		return;
	}
	for (int i = index; i < nums.size(); i++) {
		sum += nums[i];
		dfs(target, err, i + 1);
		sum -= nums[i];
		err++;
	}
}


int main() {
	vector<bool> mark(nums.size(), 0);
	int target;
	while (cin >> target) {
		cnt = 0;
		dfs(target, 0, 0);
		cout << cnt << endl;
	}
	system("pause");
	return 0;
}

 方法二：三层循环

#include <iostream>
using namespace std;
#include <vector>


vector<int> nums = 
{ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8 };

//方法二 三层循环
int solve(int target) {
	int cnt = 0;
	for (int i = 0; i < nums.size(); i++) {
		//只错一个
		if (100 - nums[i] == target) {
			cnt++;
		}
		for (int j = i + 1; j < nums.size(); j++) {
			//只错两个
			if (100 - nums[i] - nums[j] == target) {
				cnt++;
			}
			for (int k = j + 1; k < nums.size(); k++) {
				int z = 100 - nums[i] - nums[j];
				//错了三个
				for (int l = k; l < nums.size(); l++) {
					z -= nums[l];
				}
				if (z == target) cnt++;
			}
		}
	}
	return cnt;
}


int main() {
	vector<bool> mark(nums.size(), 0);
	int target;
	while (cin >> target) {
		int cnt = solve(target);
		cout << cnt << endl;
	}
	system("pause");
	return 0;
}