0416. Partition Equal Subset Sum

https://leetcode.com/problems/partition-equal-subset-sum

Description

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.

Constraints:

• 1 <= nums.length <= 200

• 1 <= nums[i] <= 100

ac1: dp

backpack problem, for 1 element, you can pick it or not.

class Solution {
    public boolean canPartition(int[] nums) {
        // edge cases
        if (nums == null || nums.length == 0) return false;

        // get array sum
        int sum = 0;
        for (int n : nums) sum += n;
        if (sum % 2 != 0) return false; // sum is odd, can't divide into 2 parts
        int target = sum / 2; // this is what we need to find

        boolean[] dp = new boolean[target+1];
        dp[0] = true; // init, empty subset add up to 0

        for (int i = 1; i < nums.length; i++) {
            for (int t = dp.length - 1; t > 0; t--) {
                if (t < nums[i]) continue;
                dp[t] = dp[t] || dp[t - nums[i]];
            }
        }

        return dp[dp.length - 1];
    }
}