416. 分割等和子集

public class Solution {

    public boolean canPartition(int[] nums) {         int len = nums.length;         if (len == 0) {             return false;         }         int sum = 0;         for (int num : nums) {             sum += num;         }

        // 特判：如果是奇数，就不符合要求         if ((sum & 1) == 1) {             return false;         }

        int target = sum / 2;         // 创建二维状态数组，行：物品索引，列：容量（包括 0）         boolean[][] dp = new boolean[len][target + 1];

        // 先填表格第 0 行，第 1 个数只能让容积为它自己的背包恰好装满         if (nums[0] <= target) {             dp[0][nums[0]] = true;         }         // 再填表格后面几行         for (int i = 1; i < len; i++) {             for (int j = 0; j <= target; j++) {                 // 直接从上一行先把结果抄下来，然后再修正                 dp[i][j] = dp[i - 1][j];

                if (nums[i] == j) {                     dp[i][j] = true;                     continue;                 }                 if (nums[i] < j) {                     dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];                 }             }         }         return dp[len - 1][target];     } }