# LeetCode416. Partition Equal Subset Sum（动态规划）

## LeetCode416. Partition Equal Subset Sum（动态规划）

• Medium
• Accepted：79,322
• Submissions：197,654

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.

### 链接

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

### 代码

Time SubmittedStatusRuntimeMemoryWay
a few seconds agoAccepted76 ms60.2 MBRecursion
11 hours agoAccepted168 ms8.4 MBDP
• 递归
class Solution {
private:
vector <vector<int> > memo;
bool solve(vector<int>& nums, int index, int C)
{
if (C == 0)
return true;
if (C < 0 || index < 0)
return false;
if (memo[index][C] != -1)
return memo[index][C];
memo[index][C] = solve(nums, index - 1, C) || solve(nums, index - 1, C - nums[index]);
return memo[index][C];
}
public:
bool canPartition(vector<int>& nums) {
int n = nums.size(), sum = 0;
for (int i = 0; i < n; ++i)
sum += nums[i];
if (n == 0 || sum % 2 == 1)
return false;
int C = sum / 2;
memo = vector <vector <int>> (n, vector<int>(C + 1, -1));
return solve(nums, n - 1, C);
}
};
• 动态规划
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size(), sum = 0;
for (int i = 0; i < n; ++i)
sum += nums[i];
if (n == 0 || sum % 2 == 1)
return false;
int C = sum / 2;
vector <bool> dp(C + 1, false);
for (int i = 0; i <= C; ++i)
dp[i] = (nums[0] == i);
for (int i = 1; i < n; ++i)
for (int j = C; j >= nums[i]; --j)
dp[j] = (dp[j] || dp[j - nums[i]]);
return dp[C];
}
};

The end.
2019年4月5日 星期五