class Solution {
    // 元素只能用一次，所以使用01背包
    // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
    // 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
    public boolean canPartition(int[] nums) {
        int sum = 0, len = nums.length;
        int[] dp = new int[10001];
        for(int i = 0; i < len; i++) sum += nums[i];
        if(sum % 2 == 1) return false;
        int target = sum / 2;

        for(int i = 0; i < len; i++){
            // 每个元素不可重复放入，所以从大到小遍历
            for(int j = target; j >= nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        // 集合中的元素正好可以凑成总和target
        return dp[target] == target;
    }
}