题解 | #数组分组#C++ 代码 （本质是考给定一个数组和目标值，能否用数组中的元素组成目标值）

//本质是考给定一个数组和目标值，能否用数组中的元素组成目标值

#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
using namespace std;
bool sum_of_target(vector<int>& vec, int size, int target)
{
	if (size == 0 && target != 0)
	{
		return false;
	}
	if (vec[size - 1] == target)
	{
		return true;
	}

	return sum_of_target(vec, size - 1, target - vec[size - 1]) || sum_of_target(vec, size - 1, target);//取或者不取该元素

}
int main()
{
	int n = 0;
	cin >> n;
	vector<int>num;
	for (int i = 0; i < n; i++)
	{
		int temp = 0;
		cin >> temp;
		num.push_back(temp);
	}
	int sum = accumulate(num.begin(), num.end(), 0);
	if (sum % 2 != 0)//注意不能使用（sum%2==1)因为可能为负数-1
	{
		cout << "false" << endl;
	}
	else
	{
		vector<int>five;
		vector<int>three;
		vector<int>other;
		for (int a : num)
		{
			if (a % 5 == 0)
			{
				five.push_back(a);
			}
			else if (a % 3 == 0)
			{
				three.push_back(a);
			}
			else
			{
				other.push_back(a);
			}
		}
		int sum_five = accumulate(five.begin(), five.end(), 0);
		int sum_three = accumulate(three.begin(), three.end(), 0);
		int sum_other = accumulate(other.begin(), other.end(), 0);
		if (sum_five == sum && three.size() == 0 && other.size() == 0)//这时候分为5的倍数数组和空数组，这部分是提交失败之后才发现有这样一个坑
		{
			cout << "true" << endl;
		}
		else
		{
			int target = 0.5*sum - sum_five;
			//cout << target << endl;
			//cout << sum_five << endl;
			sort(other.begin(), other.end());
			int size = other.size();
			if (sum_of_target(other, size, target))
			{
				cout << "true" << endl;
			}
			else
			{
				cout << "false" << endl;
			}
		}

	}
	return 0;
}