[LeetCode] Problem 416 - Partition Equal Subset Sum

Posted on | In ,

Given a non-empty array 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.

Note

  1. Each of the array element will not exceed 100.
  2. The array size will not exceed 200.

Example

No.1

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

No.2

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// dp[i] = dp[i] || dp[i - nums[j]], nums[j] <= i <= target
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;

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

    return dp[target];
}