/**
 * @param {number[]} nums
 * @return {boolean}
 * 第一种二位数组dp,dp[i][j]表示i个数字和能不能为j
 * dp[i][j] = dp[i - 1][j] || (j >= nums[i] ? dp[i - 1][j - nums[i]] : false);
 * 下面是nums[i-1], 因为nums[i-1]才表示第i个数字
 */
const canPartition1 = function (nums) {
  let dp = [];
  const sum = nums.reduce((a, b) => a + b);
  const halfSum = sum / 2;
  if ((sum & 1) === 1) {
    return false;
  }
  for (let i = 0, ii = nums.length; i <= ii; ++i) {
    dp[i] = [];
    for (let j = 0; j <= halfSum; ++j) {
      dp[i][j] = false;
    }
  }
  for (let i = 0, ii = nums.length; i <= ii; ++i) {
    dp[i][0] = true;
  }

  for (let i = 1, ii = nums.length; i <= ii; ++i) {
    for (let j = 1; j <= halfSum; ++j) {
      dp[i][j] = dp[i - 1][j] || (j >= nums[i - 1] ? dp[i - 1][j - nums[i - 1]] : false);
    }
  }
  return dp[nums.length][halfSum]
};

// dp[i], 数字i是否是, 数组任意子集之和
const canPartition = function (nums) {
  let dp = [true];
  const sum = nums.reduce((a, b) => a + b);
  const halfSum = sum / 2;
  if ((sum & 1) === 1) {
    return false;
  }
  for (let j = 1, jj = halfSum; j <= jj; ++j) {
    dp[j] = false;
  }

  for (let i = 0, ii = nums.length; i < ii; ++i) {
    // for (let j = 1, jj = halfSum; j <= jj; ++j) { 正着写不行, 如果有元素值为1,则所有的dp[j]的值为true
    for (let j = halfSum; j > 0; --j) { // 原因是因为倒着写的话dp[i] = dp[i-1] 会从大到小,最后才会触碰到dp[0] = ture这个特殊的边界条件
      // console.log(dp[j]);
      if (j >= nums[i]) {
        // console.log(dp[j - nums[i]]);
        dp[j] = dp[j] || dp[j - nums[i]];
      }
    }
  }
  console.log(dp);
  return dp[halfSum];
};