# 0416. Partition Equal Subset Sum
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Knapsack problem`
Link: https://leetcode.com/problems/partition-equal-subset-sum/
## 思路
**经典的背包问题**
因为要判断每个元素到底拿还是不拿
可以做空间优化~
## Code
### $O(mn)$ $O(mn)$

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for(int num:nums) sum += num;
        if(sum%2!=0) return false;
        boolean[][] dp = new boolean[n][sum/2+1];
        dp[0][0] = true;
        if(nums[0]<=sum/2) dp[0][nums[0]] = true;
        
        for(int i=1; i<n; i++){
            for(int j=0; j<=sum/2; j++){
                dp[i][j] |= dp[i-1][j];
                if(j-nums[i]>=0) dp[i][j] |= dp[i-1][j-nums[i]];
                if(dp[i][sum/2]) return true;
            }
        }
        return false;
    }
}

### $O(mn)$ $O(m)$

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for(int num:nums) sum += num;
        if(sum%2!=0) return false;
        boolean[] dp = new boolean[sum/2+1];
        dp[0] = true;
        if(nums[0]<=sum/2) dp[nums[0]] = true;
        
        for(int i=1; i<n; i++){
            for(int j=sum/2; j>=0; j--){
                if(j-nums[i]>=0) dp[j] |= dp[j-nums[i]];
                if(dp[sum/2]) return true;
            }
        }
        return false;
    }
}