416.分割等和子集

链接：416.分割等和子集
难度：Medium
标签：数组、动态规划
简介：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

题解 1 - typescript

• 编辑时间：2020-10-11
• 执行用时：132ms
• 内存消耗：40.4MB
• 编程语言：typescript
• 解法介绍：[参考链接](https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/fen-ge-deng-he-zi-ji-by-leetcode-solution/)。

function canPartition(nums: number[]): boolean {
  const len = nums.length;
  // 如果只有一个元素，不可能平分
  if (len < 2) return false;
  let sum = nums.reduce((total, cur) => total + cur, 0);
  let maxNum = Math.max(...nums);
  // 如果总和是奇数，不可能平分
  if (sum & 1) return false;
  const target = sum / 2;
  // 如果有数大于平分值，不可能评分
  if (maxNum > target) return false;
  const dp: boolean[] = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const num of nums) {
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }
  return dp[target];
}

题解 2 - typescript

• 编辑时间：2021-09-13
• 执行用时：228ms
• 内存消耗：60.5MB
• 编程语言：typescript
• 解法介绍：动态规划。

function canPartition(nums: number[]): boolean {
  const n = nums.length;
  const sum = nums.reduce((total, cur) => total + cur, 0);
  if (sum % 2 !== 0) return false;
  const halfSum = sum / 2;
  const dp: boolean[][] = new Array(n + 1).fill(0).map(_ => new Array(halfSum + 1).fill(false));
  for (let num = 0; num <= halfSum; num++) dp[0][num] = true;
  dp[1][nums[0]] = true;
  for (let i = 2; i <= n; i++) {
    const num = nums[i - 1];
    dp[i][0] = dp[i][num] = true;
    for (let j = 1; j <= halfSum; j++) {
      dp[i][j] = dp[i - 1][j];
      if (j < num) continue;
      dp[i][j] ||= dp[i - 1][j - num];
    }
    if (dp[i][halfSum]) return true;
  }
  return false;
}

题解 3 - typescript

• 编辑时间：2021-09-13
• 执行用时：132ms
• 内存消耗：40.4MB
• 编程语言：typescript
• 解法介绍：动态规划优化。

function canPartition(nums: number[]): boolean {
  const n = nums.length;
  const sum = nums.reduce((total, cur) => total + cur, 0);
  if (sum % 2 !== 0) return false;
  const halfSum = sum / 2;
  const dp: boolean[][] = new Array(2).fill(0).map(_ => new Array(halfSum + 1).fill(false));
  dp[1][nums[0]] = true;
  for (let i = 2; i <= n; i++) {
    const idx = i % 2;
    const prevIdx = idx ^ 1;
    const num = nums[i - 1];
    dp[idx][0] = dp[idx][num] = true;
    for (let j = 1; j <= halfSum; j++) {
      dp[idx][j] = dp[prevIdx][j];
      if (j >= num) dp[idx][j] ||= dp[prevIdx][j - num];
    }
    if (dp[idx][halfSum]) return true;
  }
  return false;
}