题解 | 数组分组

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

typedef long long ll;

int n, target;
int vis[30], a[30];

bool dfs(int deep, int *vis, int sum) {
	if (sum == target) return true;
	if (n + 1 == deep) {
		return sum == target; 
	}
	vis[deep] = 1;
	bool l = dfs(deep + 1, vis, sum + a[deep]);
	vis[deep] = 0;
	bool r = dfs(deep + 1, vis, sum);
	return l || r;
	//回溯的部分 
}

//其实和之前的全排列的那道一样的
int main() {
	int len, tmp, five_part = 0, three_part = 0, other_part = 0;
	string ans = "false";
    cin >> len;
    for (int i = 0; i < len; i++) {
    	cin >> tmp;
    	if (tmp % 5 == 0) five_part += tmp;
    	else if (tmp % 3 == 0) three_part += tmp;
    	else {
    		other_part += tmp;
    		a[++n] = tmp;
		}
	}
	int diff1 = (tmp = five_part - three_part) > 0 ? tmp : -tmp;
	int target2 = diff1 + other_part;
	if (!(target2 & 1)) {
		target = target2 / 2;
		ans =  dfs(1, vis, 0) ? "true" : "false";	
	}
    cout << ans << endl; 
}
// 64 位输出请用 printf("%lld")