> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/401-600/416.-fen-ge-deng-he-zi-ji.md).

# 416. 分割等和子集

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

## 一：dp

用`dp[i][j] = True`表示能用前i个数凑出j，False就是不能。将该题转换为01背包问题，即数组中的数能否凑出sum/2，能则说明存在一种分割方法将数组等分。

i=0表示没有数，因此i=1表示数组0号元素，即`dp[i][j]`表示能否用数组`[0...i-1]`凑出

```
dp[i][j] =  dp[i-1][j]    or    dp[i-1][j-nums[i-1]]
              不用i-1                     用i-1
```

base case

```
dp[0][j] = False	#0个数什么也凑不出
dp[i][0] = True		#0一定能凑出
```

```python
class Solution:
    def canPartition(self, nums) -> bool:
        n =len(nums)
        s = sum(nums)
        if s%2 !=0: return False	#和为奇数说明无法等分
        s = s//2
        dp = [[False]* (s+1) for _ in range(n+1)]
        for i in range(n+1):	#重点：base case
            dp[i][0] = True
        for i in range(1, n+1):
            for j in range(1,s+1):
                if j-nums[i-1] >= 0:
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[n][s]
```