题目

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:

• Each of the array element will not exceed 100.
• 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 [11].


Example 2:

Input: [1, 2, 3, 5]

Output: false

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


动态规划

要么取1，要么不取1.
[0,1]
|
1,5,11,6,...


要么不取5:  [0,1]

[0,1]
|
1,5,11,6,...


代码

class Solution {
public boolean canPartition(int[] nums){
int sum = 0;
for (int n : nums) sum += n;
if (sum % 2 == 1) return false;
int target = sum / 2;
Set<Integer> sumSet = new HashSet<>();
for (int n : nums) {
int[] newSumSet = new int[sumSet.size()];
int p = 0;
for (int s : sumSet) {
int newSum = n + s;
if (newSum == target) return true;
newSumSet[p++] = newSum;
}
for (int newSum : newSumSet) sumSet.add(newSum);
}
return false;
}
}


另外一种动态规划视角

1. 不取第i个数：dp[x] = dp[x]，即每个记录都不变。
2. 取第i个数：如果dp[x - nums[i]] == true，则dp[x] = true

dp[i] = dp[i] || dp[i - num];


代码

class Solution {
public boolean canPartition(int[] nums){
int sum = 0;
for (int n : nums) sum += n;
if (sum % 2 == 1) return false;
int target = sum / 2;
boolean[] dp = new boolean[sum + 1];
dp[0] = true;
for (int num : nums) {
for (int i = sum; i > 0; i--) {
if (i >= num) dp[i] = dp[i] || dp[i - num];
}
}
return dp[target];
}
}