# 416. Partition Equal Subset Sum

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MkN127l36pzNrU0KFTG%2F-MkNA2dkLOUP6jTBNKCY%2Fimage.png?alt=media\&token=59aac85f-843e-4d88-90b7-340a2a471461)

### 01 背包問題

<https://labuladong.github.io/algo/3/27/81/>

## transform problem into 01 **knapsack**

<https://labuladong.github.io/algo/3/27/82/>

time: (n\*m), n is nums size, m = sum/2

space: (n\*m)

```java
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) { // add them all
            sum += num;
        }
        
        if (sum % 2 == 1) { // if two sets are equal, sum must be even
            return false;
        }
        
        int n = nums.length;
        int m = sum/2; // become 01 backpack problems, target is sum/2
        
        boolean dp[][] = new boolean[n+1][m+1];
        
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (j >= nums[i-1]) {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][m]; // when sum/2 (two sets are equal), is it true?
    }
}
```

## 1D space

T: O(mn)

S: O(n)

```java
class Solution {
    public boolean canPartition(int[] nums) {
        
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int m = nums.length;
        int n = sum/2;
        boolean[] dp = new boolean[n+1]; // 0 ~ m number, 0~n weight
        
        dp[0] = true;
        for (int i = 1; i <= m; i++) {
            for (int j = n; j >= 0; j--) { // when go to 1D, should reverse to do, or will become complete kapnack
                
                int curr = nums[i-1]; // i-1 !
                if (j >= curr) {
                    // choose or not choose
                    dp[j] |= dp[j - curr];
                }
            }
        }
        return dp[n]; // we want sum/2
    }
}ja
```

或者把 j >= nums\[i-1] 寫在 for loop 就可以了, 少一個 if 條件

````java
```java
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }

        int m = nums.length;
        int n = sum/2;
        boolean[] dp = new boolean[n+1];
        dp[0] = true; // sum == 0, always true

        for (int i = 0; i < m; i++) {
            for (int j = n; j >= nums[i]; j--) {
                dp[j] = dp[j] ||  dp[j - nums[i]];
            }
        }
        return dp[n];
    }
}
```
````