题解 | JAVA #分割等和子集# [P2]

题目明显可以转化为“是否存在和为sum/2的子数组”
所以就先求和，除以2，得出target sum

定义dp[i][s]
如果dp[i][s]=true, 表示nums[0, i]中存在一个subset的和为s

那么对于第i个数，能凑出s有两种情况：
  1. 之前i-1个数已经能凑出s
  2. 之前i-1的数能凑出s-num[i]
所以，dp[i][s] = dp[i-1][s] || dp[i-1][s-nums[i]]；

然后就正常2D->1D空间优化，只需要存dp[s]

空间：O(maxSum)
时间：O(maxSum * n)

import java.util.*;

public class Solution {
    public boolean partition (int[] nums) {
      int sum = 0;
      for (int n : nums) { sum += n; }
      if ((sum & 1) == 1) return false;  // odd
      sum = sum >> 1;  // sum/2
      
      boolean[] dp = new boolean[sum+1];
      dp[0] = true;
      
      for (int n : nums) {
        // short-circuit
        if (dp[sum]) return true;
        // loop backward to prevent dirty read
        for (int s = sum; s > 0; s--) {
          if (s - n >= 0) 
            dp[s] = dp[s] || dp[s-n];
        }
      }

      return dp[sum];
    }
}