416. Partition Equal Subset Sum

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Code

322. Coin Change和本题

• 322: 无限硬币找和; 416: 有限硬币找和
• 322: 先遍历和再遍历硬币; 416: 先遍历硬币再遍历和

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;

        for (int num : nums) {
            sum += num;
        }

        if (sum % 2 != 0) {
            return false;
        }

        int target = sum / 2;

        int n = nums.length;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int currSum = target; currSum > 0; currSum--) {
                if (currSum - num >= 0) {
                    dp[currSum] = dp[currSum] || dp[currSum - num];
                }
            }
        }

        return dp[target];
    }
}