> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/l4dong-tai-gui-hua/partition-equal-subset-sum.md).

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

**Example 2:**

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

Output: false

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

分析

01背包需要倒序，因为使用滚动数组，所以数组是一维的，d\[i]需要从前一个d\[i-1]得到，因此需要倒序。

```
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sm = sum(nums)
        if sm%2!=0:
            return False
        t = sm//2
        n = len(nums)
        p = [False]*(t+1)
        p[0] = True


        for i in range(n):
            for j in range(t,0,-1):#01背包，需要倒着，因为需要i-1的值。
                if j - nums[i] >= 0 and p[j - nums[i]]:
                    p[j] = True#没有break，否则之后的J都不再计算了。


        return p[t]
```