数组分组

import java.util.Scanner;
import java.util.ArrayList;

// 用递归很方便，但要注意一个坑：如果用remove方法每次都把传入的数组弹出，最终会导致无法恢复现场
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        ArrayList<Integer> normal = new ArrayList<>();
        int fivesum = 0, threesum = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] % 5 == 0) {;
                fivesum += nums[i];
            } else if (nums[i] % 3 == 0) {
                threesum += nums[i];
            } else {
                normal.add(nums[i]);
            }
        }
        System.out.println(canEqual(threesum, fivesum, normal, 0));
    }

    public static boolean canEqual(int three, int five, ArrayList<Integer> normal, int index) {
        if (index == normal.size()) {
            if (three == five) {
                return true;
            }
            return false;
        } else {
            int curr = normal.get(index);
            return canEqual(three + curr, five, normal, index+1) || canEqual(three, five + curr, normal, index+1);
        }
    } 
}

import java.util.ArrayList;
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        ArrayList ao = new ArrayList();
        int sum5 = 0;
        int sum3 = 0;
        int sumo = 0;
        while(in.hasNextInt()){
            int a = in.nextInt();
            if(a%5 == 0){
                sum5 += a;
            } else if(a%3 == 0){
                sum3 += a;
            } else {
                ao.add(a);
                sumo += a;
            }
        }
        if((sum5 + sum3 + sumo)%2 != 0){
            System.out.print(false);
        } else {
            int sum = (sum3 + sum5 + sumo)/2 -sum5;
            if(cansum(ao, ao.size() - 1, sum)){
                System.out.print(true);
            } else {
                System.out.print(false);
            }
        }
    }
    private static boolean cansum(ArrayList a, int i, int sum){
        if(a.size() == 0 || i < 0){
            return sum == 0;
        }
        return cansum(a, i - 1 , sum) || cansum(a, i - 1, sum - a.get(i));
    }
}

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static Stack<Integer> stack = new Stack();
    public static boolean flag = false;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        int[] a = new int[n];
        int sum3 = 0;
        int sum5 = 0;
        for(int i = 0; i < n; i++){
            a[i] = in.nextInt();
            if(a[i]%3 == 0){
                sum3 += a[i];
            }else if(a[i] % 5 == 0){
                sum5 += a[i];
            }else{
                stack.push(a[i]);
            }
        }
        dfs(sum3, sum5);
        System.out.println(flag);
    }

    public static void dfs(int sum3, int sum5) {
        if (stack.empty() && sum3 == sum5) {
            flag = true;
        }
        if (!stack.empty()) {
            int n = stack.pop();
            dfs(sum3+n, sum5);
            dfs(sum3, sum5+n);
            stack.push(n);
        }
    }
}

// 用的递归，很方便，不知道正确性，欢迎大家指正
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = in.nextInt();
            }

            boolean result = canPartition(nums, 0, 0, 0);
            System.out.println(result ? "true" : "false");
        }

        in.close();
    }

    // 递归的方式解决，index表示当前的数字在数组中的位置，sum1表示第一组数的和，sum2表示第二组数的和
    private static boolean canPartition(int[] nums, int index, int sum1, int sum2) {
        // 递归的终止条件，当遍历到最后一位时，检查sum1是否等于sum2，如相等，则返回true
        if (index == nums.length) {
            return Math.abs(sum1 - sum2) == 0;
        }
        // 将5放进第一组数，sum1加上该数，index + 1表示遍历到下一组数
        if (nums[index] % 5 == 0) {
            return canPartition(nums, index + 1, sum1 + nums[index], sum2);
        } else if (nums[index] % 3 == 0) {  //将3放进第二组数
            return canPartition(nums, index + 1, sum1, sum2 + nums[index]);
        } else {
            // 尝试把非3非5的数放进第一组
            if (canPartition(nums, index + 1, sum1 + nums[index], sum2)) {
                return true;
            }

            // 尝试把非3非5的数放进第二组
            if (canPartition(nums, index + 1, sum1, sum2 + nums[index])) {
                return true;
            }
        }
        // 所有的方法都没法分，返回false
        return false;
    }
}

import java.io.*;
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while ((str = br.readLine()) != null) {
            int n = Integer.parseInt(str);
            String[] strArr = br.readLine().split(" ");
            ArrayList<Integer> list = new ArrayList<>();
            int sum3=0,sum5=0,sum=0;
            for (String s : strArr){
                int num=Integer.parseInt(s);
                // 3的倍数则加到sum3
                if(num%3==0) sum3 += num;
                // 5的倍数则加到sum5
                else if(num%5==0) sum5 += num;
                // 不是3、5的倍数则加到集合中
                else list.add(num);
                // 所有数之和
                sum+=num;
            }
            // 两个相等的数之和为偶数，如果sum不为偶数，说明两个数组的和不相等
            if(sum%2!=0) System.out.println(false);
            else{
                // target代表能与sum3相加得到sum/2的值，即判断list是否存在和或值为target的元素，
                // 即用list的元素凑出target
                // 假设存在满足条件的元素，则得：sum=sum3+sum5+c（list的元素和）和sum/2=sum3+a
                // 由此可得sum/2=sum5+（c-a），即若能凑出a使得sum/2=sum3+a，则list剩余元素和+sum5
                // 必等于sum/2，所以target可以为sum/2-sum3或者sum/2-sum5
                int target=sum/2-sum3;
                System.out.println(solution(list,target,0));
            } 
        }
    }
    private static boolean solution(List<Integer>list, int target, int index) {
        // 递归终止条件
        if (index == list.size()) return target==0;
        // 核心在target-list.get(index)，在solution(list,target-list.get(index),index+1)中
        // 由于index+1，所以它会依次减去list中的元素，直到index == list.size()（即减完最后一个元素），
        // 而solution(list,target,index+1)则表示跳过第index个元素进入递归，即target不减第index个元素，
        // 所以每次递归都会出现减或者不减第index个元素的情况，因此递归终止时，完成了对list中元素所有可能类型
        // 的拼凑。当index == list.size()递归终止时，如果 target==0，说明能在list元素中凑出sum/2-sum3。
        // 可对list={1,2,5,7}进行纸上递归计算演示
        return solution(list,target-list.get(index),index+1)||solution(list,target,index+1);
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList<Integer> list = new ArrayList<>();//排除3、5倍数后剩下的数
        HashSet<Integer> differs = new HashSet<>();//能构造出的差值的集合
        int d = 0;
        for (int i = 0; i < n; i++) {//算出3、5数组分配完后之间的和的差值d
            int a = in.nextInt();
            if (a % 5 == 0) {
                d += a;
            }
            else if (a % 3 == 0) {
                d -= a;
            }
            else {
                list.add(a);
            }
        }
        d = Math.abs(d);//接下来我们要判断是否可以借助余下的数构造出d这个差值
        differs.add(0);//余下的数一个都没用的时候构造出的差值为0
        for (int x : list) {//计算出当多使用了list中的一个数x的时候，能构造出的差值集合
            HashSet<Integer> toAdd = new HashSet<>();
            for (int y : differs) {//新的能构造出的差值集合是原先能构造出的差值加减新使用的数x，符号对应x放置于哪边的数组
                toAdd.add(Math.abs(x - y));//同样，符号改变只让放置方式镜像，这里简便处理为绝对值
                toAdd.add(Math.abs(x + y));
            }
            differs = toAdd;
        }
        System.out.print(differs.contains(d));//看看差值集合里面能不能找到d，找到了就宣布构造成功。
    }
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        LinkedList<Integer> list = new LinkedList<>();
        int sum5 = 0;
        int sum3 = 0;
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            int num = in.nextInt();
            if (num % 5 == 0) {
                sum5 += num;
            } else if (num % 3 == 0) {
                sum3 += num;
            } else {
                list.add(num);
            }
        }
        int cha = Math.abs(sum3 - sum5);
        System.out.print(isDivide(cha, list));
    }
    public static boolean isDivide(int cha, LinkedList<Integer> scList) {
        LinkedList<Integer> list = new LinkedList<>(scList);
        if (list.size() == 0) {
            return cha == 0;
        } else {
            int listFirst = list.poll();
            int newCha1 = Math.abs(listFirst + cha);
            int newCha2 = Math.abs(listFirst - cha);
            return isDivide(newCha1, list) || isDivide(newCha2, list);
        }
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), part = 0, low = 0, sum = 0;
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = in.nextInt();
        }
        ArrayList<Integer> nums = new ArrayList<>();
        for(int num : arr){
            if(num % 5 != 0 && num % 3 != 0){
                nums.add(num);
            }
            if(num % 5 == 0){
                part += num;
            }
            if(num < 0){
                low += num;
            }
            sum += num;
        }
        if(sum % 2 != 0){
            System.out.println(false);
            return;
        }
        // 因为有负数，选择使用map
        HashMap<Integer, Boolean> dp = new HashMap<>();
        dp.put(0, true);
        for(int num : nums){
            dp.put(num, true);
        }
        Collections.sort(nums);
        // 使用类似0/1背包问题类似的思路
        for(int i = 0; i < nums.size(); i++){
            for(int j = sum / 2 - part; j >= low; j--){
                if(!dp.getOrDefault(j, false)){
                    dp.put(j, dp.getOrDefault(j - nums.get(i), false));
                }
            }
        }
        if(dp.getOrDefault(sum / 2 - part, false))
            System.out.println(true);
        else
            System.out.println(false);
    }
}

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num=in.nextInt();
        int sum3=0;
        int sum5=0;
        ArrayList<Integer> listO=new ArrayList<>();
        for(int i=0;i<num;i++){
            int temp=in.nextInt();
            if(temp%3==0){
                sum3+=temp;//含3 
            }else if(temp%5==0){
                sum5+=temp;//含5
            }else{
                listO.add(temp);// 不含的先不加
            }
        }
        int len=1;
        for(int i=1;i<=listO.size();i++){//每个中立元素都有2种可能
            len*=2;
        }
        for(int i=0;i<len;i++){//遍历每个元素的每种可能
            int sum3Temp=sum3;
            int sum5Temp=sum5;
            int iTemp=i;
            for(int j=0;j<listO.size();j++){//用%2来决定加入哪个数组
                if( iTemp%2==1){
                    sum3Temp+=listO.get(j);
                }else{
                    sum5Temp+=listO.get(j);
                }
                iTemp/=2;
            }
            if(sum3Temp==sum5Temp){
                System.out.print(true);
                return;
            }
        }
        System.out.print(false);
    }
}