416. Partition Equal Subset Sum

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)

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)

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
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];
    }
}
```