Backpack - 416. Partition Equal

// dp[j] = dp[j] || dp[j - nums[i]]         (nums[i] <= j <= target)

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num: nums) {
            sum += num;
        }
        if (sum % 2 == 1) {
            return false;
        }
        
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        
        // 这个解法不对，对于 [1, 2, 5] 会返回 true，实际上应为 false
        // 原因是 dp index 从 num to target，会涉及到元素的重复使用。num: 2, 会将 dp[4] 赋值为 true，原因是 dp[4] |= dp[4 - 2]，这里的 2 使用了两次。而从 target 到 num 的方向，就不会对该下 num 重复使用。
        // for (int num: nums) {
        //     for (int i = num; i <= target; i++) {
        //         dp[i] |= dp[i - num];
        //     }
        // }
        
        for (int num: nums) {
            for (int i = target; i >= num; i--) {
                dp[i] |= dp[i - num]; 
            }
        }
        
        return dp[target];
    }
}