# LeetCode 416. Partition Equal Subset Sum

## Description

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, 5, 11, 5]`
`输出: true`

`输入: [1, 2, 3, 5]`

### 思路

`转移方程为：dp[i][j] = dp[i - 1][j] if dp[i - 1][j] else dp[i - 1][j - nums[i]]`
```# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-10-26 09:30:29

from typing import List

class Solution:
def canPartition(self, nums: List[int]) -> bool:
sum_nums = sum(nums)
if sum_nums & 1 or max(nums) > (sum_nums >> 1):
return

half_sum = sum_nums >> 1
nums.sort(reverse=True)
dp = [[False] * (half_sum + 1) for _ in range(2)]
dp[0][0] = True
dp[0][nums[0]] = True

for i in range(1, len(nums)):
idx = i % 2
for j in range(nums[i]):
dp[idx][j] = dp[idx - 1][j]
for j in range(nums[i], half_sum + 1):
dp[idx][j] = dp[idx - 1][j] if dp[idx - 1][j] else dp[idx - 1][j - nums[i]]
if dp[idx][-1]:
return True

return dp[-1][-1]
```