题解 | #分割等和子集#

import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int []num=new int[n];
        for(int i=0;i<n;i++){
            num[i]=input.nextInt();
        }
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=num[i];
        }
        if(sum%2==1){
            System.out.println(false);
            return;
        }
        sum=sum/2;
        int []dp=new int[sum+1];   //价值是num[i],重量也是num[i]，重量>=价值
        for(int i=0;i<n;i++){
          for(int j=sum;j>=num[i];j--){
              dp[j]=Math.max(dp[j],dp[j-num[i]]+num[i]);
          }
        }
        if(dp[sum]==sum){
            System.out.println(true);
        }
        else{
            System.out.println(false);
        }
    }
    
}