201301 JAVA题目0-1级 (HJ93)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
using namespace std;

bool DFS(vector<int> &nums, vector<bool> &visited, int sum)
{
    if (sum == 0) return true;
    for (int i = 0; i < visited.size(); ++i)
    {
        if (visited[i] == false)
        {
            visited[i] = true;
            if (DFS(nums, visited, sum - nums[i]))
                return true;
            visited[i] = false;
        }
    }
    return false;
}

int main(void)
{
    int n, tmp;
    while (cin >> n)
    {
        bool flag = true;
        vector<int> array_rest;
        vector<int> array_5;
        vector<int> array_3;
        for (int i = 0; i < n; ++i)
        {
            cin >> tmp;
            if (tmp % 5 == 0)
                array_5.push_back(tmp);
            else if (tmp % 3 == 0)
                array_3.push_back(tmp);
            else
                array_rest.push_back(tmp);
        }
        
        // 首先对3组数据求和，分别是3的倍数，5的倍数和剩下的
        int sum_3 = std::accumulate(array_3.begin(), array_3.end(),0);
        int sum_5 = std::accumulate(array_5.begin(), array_5.end(),0);
        int sum_rest = std::accumulate(array_rest.begin(), array_rest.end(), 0);
        int diff = abs(sum_3 - sum_5);
        // 然后用深度优先遍历找到是否存在解，
        // 因为2*x + diff = sum_rest
        // 所以x = [sum_rest-diff]/2     
        // 因此用深度遍历找到array_rest中是否存在和为x的一组数就可以了
        if ((sum_rest - diff) % 2 != 0)
        {
            flag = false; // 不能整除就无解
        }
        else
        {
            int goal = (sum_rest - diff) / 2;
            vector<bool> visited(array_rest.size(), false);
            if (!DFS(array_rest, visited, goal))
                flag = false;
        }
        if (flag)
            cout << "true" << endl;
        else
            cout << "false" << endl;
    }
}