# 416. Partition Equal Subset Sum (Medium)

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

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 1:

```Input: [1, 5, 11, 5]

Output: true

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

Example 2:

```Input: [1, 2, 3, 5]

Output: false

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

## Solutions

``````class Solution {

// This problem can be translated as find x numbers of which the total summation is sum/2,
// where x is a variable and not determined; sum is the total summation of elements in nums.

public boolean canPartition(int[] nums) {
if (nums == null || nums.length <= 1) {
return false;
}

int len = nums.length;

int sum = 0;
for (int i = 0; i < len; i++) {
sum += nums[i];
}

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

int target = sum / 2;
boolean[][] dp = new boolean[target + 1][len + 1];

// target 0, it is easy to get
Arrays.fill(dp, true);

// for the first column all set false, literally, elements in nums starts from 1 in dp
for (int i = 0; i < target + 1; i++) {
dp[i] = false;
}

dp = true;

// i is the target to achieve
for (int i = 1; i < target + 1; i++) {

// we add (j-1)th num to gain i
for (int j = 1; j < len + 1; j++) {

// can I use result of dp[i][j-1] or incorporate nums[j-1] to come up with a new combination.

// 1. dp[i][j-1] is true which means elements in nums[0:j-2] can make sum to i, and we don't
// have to use nums[j-1]
if (dp[i][j - 1]) {
dp[i][j] = true;

continue;
}

// 2. dp[i - nums[j - 1]][j - 1] is true which means we can use nums[i-j], plus valid combination
// of target i-nums[j-1] of which elements are selected from nums[0:j-2] to achieve target i.

dp[i][j] = i >= nums[j - 1] && dp[i - nums[j - 1]][j - 1];
}
}

return dp[target][len];
}
}
``````

## Incorrect Solutions

``````class Solution {

// Incorrection idea.

// This problem can be translated as find x numbers of which the total summation is sum/2,
// where x is a variable and not determined; sum is the total summation of elements in nums.

public boolean canPartition(int[] nums) {
if (nums == null || nums.length <= 1) {
return false;
}

int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}

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

int target = sum / 2;

for (int i = 0; i <= target; i++) {

}

boolean ans = false;

return ans;
}
}
``````