题解 | #分割等和子集#

import java.util.*;
public class Main{

    public static boolean process(int[] arr,int n){
        int sum=0;
        for(int a:arr)
            sum+=a;
        if((sum&1)!=0)
            return false;
        int bag=sum/2;
        int[]dp=new int[bag+1];
        Arrays.fill(dp,Integer.MIN_VALUE);
        dp[0]=0;
        for(int i=1;i<=bag;i++){
            for(int j=0;j<arr.length;j++){
                if(arr[j]<=i&&dp[i-arr[j]]!=Integer.MIN_VALUE){
                    dp[i]=Math.max(dp[i],dp[i-arr[j]]+1);
                }
            }
        }
        return dp[bag]==Integer.MIN_VALUE?false:true;
    }
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[]arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        System.out.print(process(arr,n));
    }
}