416. Partition Equal Subset Sum.md

### 416.  Partition Equal Subset Sum



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

难度:

Medium 

记得算法考试考过证明这个问题是NP的，当时用的是subset sum是NP，然后来证明这个？如果我们能找到一个subset的sum是整个array sum的一半，那么问题解决。subset sum我们又可以继续转化，转成背包问题。

值得注意的是，这是subset sum，并不是subarray sum(这个明显要简单一些，因为subarray是连着的).

subset sum也是有自己的[wikipedia page](https://en.wikipedia.org/wiki/Subset_sum_problem).



当然，这也是一个subset problem，我们当然也可以用subset，加入和不加入，但是worst case O(2^n).



对于subset sum的递推方程式:

subset(arr,n,s) = subset(arr,n-1,s) or subset(arr, n-1, s- arrp[n-1])



画表可以开始，第一列全为1，是因为不选全部可以为0



```
	0	1	2	3	4	5	6	8	9	10	11
0	1	0	0	0	0	0	0	0	0	0	0
1	1	1	0	0	0	0	0	0	0	0	0
5	1	1	0	0	0	1	1	0	0	0	0
5	1	1	0	0	0	1	1	0	0	0	1
```



所以伪多项式算法写出来

AC代码



```
class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        def subset(nums, s):
        	dp = [[0 for i in range(s+1) ] for j in range(len(nums)+1)]

        	dp[0][0] = 1
        	# init the first col
        	for i in range(len(nums)+1 
        		dp[i][0] = 1

        	for i in range(1,len(nums)+1):
        		for j in range(1,s+1):
        			if dp[i-1][j] == 1:
        				dp[i][j] = 1
        			elif j >= nums[i-1] and dp[i-1][j-nums[i-1]] ==1:
        				dp[i][j]  = 1
        	return dp[-1][-1] == 1



        total = sum(nums)
        if total % 2 == 1:
        	return False
        else:
        	half = total / 2
        	return subset(nums,half) == 1

```



当然可以小调整，比如一旦发现，提前return等等，但是时间上依旧是后20%,不知道时间上快很多的人是如何做到的|||