题解 | #数组分组#

基本思路是用深度优先搜索DFS遍历所有可能，用了一个setidx的集合保存数组下标，因为这个是多维的，最多可能50个维度，用多维数组没法表示。

DFS递归的思路，i个数的和sum[i] = sum[i-1] + a[j]; j 从0-n，且j不在集合setidx中。

最后就是一些边际条件要小心，这个调试一下就能过了。

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

int target;
set<int> setidx;	//用于保存数组下标
vector<int> v5;		//保存5的倍数
vector<int> v3;		//保存3的倍数
vector<int> vx;		//保存非5和3倍数的数

bool DFSSum(set<int> &setidx, int index, vector<int> &vx, int sum)
{
	if (setidx.count(index) == 1)
	{
		return false;
	}

	if (sum + vx[index] == target)
	{
		//打印分组数据
// 		for (auto it : v5)
// 		{
// 			cout << it << " ";
// 		}
// 
// 		for (auto it : setidx)
// 		{
// 			cout << vx[it] << " ";
// 		}
// 
// 		cout << vx[index] << endl;
		return true;
	}

	sum += vx[index];
	setidx.insert(index);

	for (size_t i=0; i<vx.size(); i++)
	{
		bool res = DFSSum(setidx, int(i), vx, sum);
		if (res)
		{
			return true;
		}	
	}

	setidx.erase(index);

	return false;
	
}

int main()
{
	int sum = 0;
	int s5 = 0;
	int s3 = 0;
	int n;
	bool ret = false;

	//while (1)
	{
		setidx.clear();
		v5.clear();
		v3.clear();
		vx.clear();
		sum = 0;
		s5 = 0;
		s3 = 0;
		ret = false;

		cin >> n;

		while (n-- > 0)
		{
			int num;
			cin >> num;
			sum += num;
			if (num % 5 == 0)
			{
				v5.push_back(num);
				s5 += num;
			}
			else if (num % 3 == 0)
			{
				v3.push_back(num);
				s3 += num;
			}
			else
			{
				vx.push_back(num);
			}
		}

		int Max = max(s5, s3);

		if (abs(sum % 2)== 1) {
			cout << "false" << endl;
			return 0;
		}

        if (Max == sum/2)
        {
            cout << "true" << endl;
            return 0;
        }

		target = sum / 2 - Max;

		for (size_t k = 0; k < vx.size(); k++)
		{
			ret = DFSSum(setidx, int(k), vx, 0);
			if (ret)
			{
				cout << "true" << endl;
				break;
			}
		}

		if (!ret)
		{
			cout << "false" << endl;
		}
	}

    return 0;

}