题解 | #数组分组#

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

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // 去掉0
        vector<int> nonZeroNums;
        for (int num : nums) {
            if (num != 0) nonZeroNums.push_back(num);
        }
        
        // 分类统计
        vector<int> group5, group3, others;
        int sum5 = 0, sum3 = 0;
        
        for (int num : nonZeroNums) {
            if (num % 5 == 0) {
                group5.push_back(num);
                sum5 += num;
            } else if (num % 3 == 0) {
                group3.push_back(num);
                sum3 += num;
            } else {
                others.push_back(num);
            }
        }
        
        return dfs(others, 0, sum5 - sum3);
    }
    
private:
    bool dfs(vector<int>& nums, int index, int diff) {
        if (index == nums.size()) {
            return diff == 0;
        }
        
        // 尝试将当前数字加入第一组（5的倍数组）
        if (dfs(nums, index + 1, diff + nums[index])) {
            return true;
        }
        
        // 尝试将当前数字加入第二组（3的倍数组）
        if (dfs(nums, index + 1, diff - nums[index])) {
            return true;
        }
        
        return false;
    }
};

int main() {
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }
        Solution sol;
        cout << (sol.canPartition(nums) ? "true" : "false") << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = sc.nextInt();
            }
            System.out.println(canPartition(nums) ? "true" : "false");
        }
    }
    
    public static boolean canPartition(int[] nums) {
        // 去掉0
        List<Integer> nonZeroNums = new ArrayList<>();
        for (int num : nums) {
            if (num != 0) nonZeroNums.add(num);
        }
        
        // 分类统计
        List<Integer> group5 = new ArrayList<>();
        List<Integer> group3 = new ArrayList<>();
        List<Integer> others = new ArrayList<>();
        int sum5 = 0, sum3 = 0;
        
        for (int num : nonZeroNums) {
            if (num % 5 == 0) {
                group5.add(num);
                sum5 += num;
            } else if (num % 3 == 0) {
                group3.add(num);
                sum3 += num;
            } else {
                others.add(num);
            }
        }
        
        return dfs(others, 0, sum5 - sum3);
    }
    
    private static boolean dfs(List<Integer> nums, int index, int diff) {
        if (index == nums.size()) {
            return diff == 0;
        }
        
        // 尝试将当前数字加入第一组（5的倍数组）
        if (dfs(nums, index + 1, diff + nums.get(index))) {
            return true;
        }
        
        // 尝试将当前数字加入第二组（3的倍数组）
        if (dfs(nums, index + 1, diff - nums.get(index))) {
            return true;
        }
        
        return false;
    }
}

def can_partition(nums):
    # 特殊处理0
    nums = [x for x in nums if x != 0]  # 去掉0
    
    # 分类统计
    group5 = []  # 5的倍数
    group3 = []  # 3的倍数（不含5的倍数）
    others = []  # 其他数
    
    for num in nums:
        if num % 5 == 0:
            group5.append(num)
        elif num % 3 == 0:
            group3.append(num)
        else:
            others.append(num)
    
    sum5 = sum(group5)
    sum3 = sum(group3)
    
    def dfs(index, diff):
        if index == len(others):
            return diff == 0
            
        # 尝试将当前数字加入第一组（5的倍数组）
        if dfs(index + 1, diff + others[index]):
            return True
            
        # 尝试将当前数字加入第二组（3的倍数组）
        if dfs(index + 1, diff - others[index]):
            return True
            
        return False
    
    return dfs(0, sum5 - sum3)

# 主程序
while True:
    try:
        n = int(input())
        nums = list(map(int, input().split()))
        print("true" if can_partition(nums) else "false")
    except:
        break