题解 | #数组分组#

#include <iostream>
#include <vector>
#include <numeric>
#include <map>

using namespace std;

vector<long long> C;
map<pair<int, long long>, bool> memo;

bool can_find_sum(int index, long long target) {
    // 基本情况：target 达到了 0，成功
    if (target == 0) {
        return true;
    }
    // 基本情况：数组遍历完或 target 变为负数（对于仅正数情况）
    if (index == C.size()) {
        return false;
    }
    // 检查备忘录
    if (memo.count({index, target})) {
        return memo[{index, target}];
    }

    // 方案一：不选择 C[index]
    if (can_find_sum(index + 1, target)) {
        return memo[{index, target}] = true;
    }

    // 方案二：选择 C[index]
    if (can_find_sum(index + 1, target - C[index])) {
        return memo[{index, target}] = true;
    }

    // 两种方案都不可行
    return memo[{index, target}] = false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    long long sum5 = 0;
    long long sum3 = 0;
    long long total_sum = 0;

    for (int i = 0; i < n; ++i) {
        long long val;
        cin >> val;
        total_sum += val;
        if (val % 5 == 0) {
            sum5 += val;
        } else if (val % 3 == 0) {
            sum3 += val;
        } else {
            C.push_back(val);
        }
    }

    if (total_sum % 2 != 0) {
        cout << "false" << endl;
        return 0;
    }

    long long target = total_sum / 2 - sum5;

    if (can_find_sum(0, target)) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }

    return 0;
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {
    private static List<Long> C = new ArrayList<>();
    private static Map<String, Boolean> memo = new HashMap<>();

    private static boolean canFindSum(int index, long target) {
        if (target == 0) {
            return true;
        }
        if (index == C.size()) {
            return false;
        }
        
        String key = index + ":" + target;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        // 不选择 C[index]
        if (canFindSum(index + 1, target)) {
            memo.put(key, true);
            return true;
        }

        // 选择 C[index]
        if (canFindSum(index + 1, target - C.get(index))) {
            memo.put(key, true);
            return true;
        }

        memo.put(key, false);
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        long sum5 = 0;
        long sum3 = 0;
        long totalSum = 0;

        for (int i = 0; i < n; i++) {
            long val = sc.nextLong();
            totalSum += val;
            if (val % 5 == 0) {
                sum5 += val;
            } else if (val % 3 == 0) {
                sum3 += val;
            } else {
                C.add(val);
            }
        }

        if (totalSum % 2 != 0) {
            System.out.println("false");
            return;
        }

        long target = totalSum / 2 - sum5;

        if (canFindSum(0, target)) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }
    }
}

import sys

# 增加递归深度限制
sys.setrecursionlimit(2000)

n = int(input())
nums = list(map(int, input().split()))

sum5 = 0
sum3 = 0
C = []
total_sum = 0

for x in nums:
    total_sum += x
    if x % 5 == 0:
        sum5 += x
    elif x % 3 == 0:
        sum3 += x
    else:
        C.append(x)

memo = {}

def can_find_sum(index, target):
    if target == 0:
        return True
    if index == len(C):
        return False
    
    # 检查备忘录
    if (index, target) in memo:
        return memo[(index, target)]
    
    # 方案一：不选择 C[index]
    res1 = can_find_sum(index + 1, target)
    
    # 方案二：选择 C[index]
    res2 = can_find_sum(index + 1, target - C[index])
    
    # 存储结果并返回
    memo[(index, target)] = res1 or res2
    return memo[(index, target)]

if total_sum % 2 != 0:
    print("false")
else:
    target = total_sum // 2 - sum5
    if can_find_sum(0, target):
        print("true")
    else:
        print("false")