// @Title: 分割等和子集 (Partition Equal Subset Sum)
// @Author: qisiii
// @Date: 2024-09-24 00:17:43
// @Runtime: 33 ms
// @Memory: 56 MB
// @comment: 
// @flag: 
class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int i:nums){
            sum+=i;
        }
        if(sum%2!=0){
            return false;
        }
        Arrays.sort(nums);
        //背包的重量为sum/2;
        //物品i的重量和价值位nums[i]，最终要判断dp[i][sum/2]==sum/2;
        int weight=sum/2;
        int[][] dp=new int[nums.length][weight+1];
        for(int j=nums[0];j<=weight;j++){
            dp[0][j]=nums[0];
        }
        for(int i=1;i<nums.length;i++){
            for(int j=1;j<=weight;j++){
                if(j<nums[i]){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
                }
            }
        }
        return dp[nums.length-1][weight]==weight;
    }
}