# 416. Partition Equal Subset Sum 分割等和子集

@TOC

## # 题目描述

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 [11].
``````

Example 2:

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

Output: false

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

## # 解题方法

### # DFS

Python代码：

``````class Solution:
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
_sum = sum(nums)
div, mod = divmod(_sum, 2)
if mod or max(nums) > div: return False
nums.sort(reverse = True)
target = [div] * 2
return self.dfs(nums, 0, target)

def dfs(self, nums, index, target):
for i in range(2):
if target[i] >= nums[index]:
target[i] -= nums[index]
if target[i] == 0 or self.dfs(nums, index + 1, target): return True
target[i] += nums[index]
return False
``````

### # 动态规划

``````dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]
``````

``````class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
const int N = nums.size();
int target = sum >> 1;
if (sum % 2 != 0) return false;
//dp[i][j] means whether we can sum to j using first i numbers.
vector<vector<bool>> dp(N + 1, vector<bool>(sum + 1, false));
// every number can build number 0.
for (int i = 0; i <= N; ++i) {
dp[i][0] = true;
}
// but for position 0, it can build number nothing.
for (int j = 1; j <= target; ++j) {
dp[0][j] = false;
}
// anyway, position 0 can build number 0.
dp[0][0] = true;
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= target; ++j) {
if (j >= nums[i - 1])
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
else
dp[i][j] = dp[i - 1][j];
}
}
return dp[N][target];
}
};
``````

``````dp[j] = dp[j] || dp[j - nums[i]]
``````

``````class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
const int N = nums.size();
if (sum % 2 != 0) return false;
int target = sum >> 1;
vector<bool> dp(sum + 1, false);
dp[0] = true;
for (int num : nums) {
for (int j = target; j >= num; --j) {
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
}
};
``````

## # 日期

2018 年 4 月 2 日 —— 要开始准备ACM了 2019 年 1 月 8 日 —— 别熬夜，我都开始有黑眼圈了。。