题目

题目来源：力扣（LeetCode）

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。


示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

思路分析

可达数组： 在某种情况下，可以达到某个值
1、计算元素组的和值
2、判断原数组的数字是否可以凑出和值的一半，可以凑出来证明可以被分割
3、状态定义：f[i][j]，前i个数字是是否能凑出j值。分成两种情况
4、动态转移方程：f[i][j] = f[i-1][j] / f[i-1][j-num[i]];
f[i-1][j]：没有使用第i个数字
f[i-1][j-num[i]]：使用第i个数字 ，剩余数字等于前i-1个数字，拼凑j-num[i] 这两个状态，只要有一个状态是1， f[i][j] = 1，前i个数字可以拼凑出来j,前i个数字到j是可达的；

  1. var canPartition = function (nums) {
  2.   let sum = 0;
  3.   for (const x of nums) sum += x;
  4.   // 特殊判断，如果数组元素的和值是一个奇数，直接返回false
  5.   if (sum % 2) return false;
  6.   const dp = new Array(sum + 1);
  7.   // 一开始所有的状态都是0，都是不可达
  8.   for (let i = 1; i <= sum; i++) dp[i] = 0;
  9.   dp[0] = 1;
  10.   sum = 0;//当前值之前所有值能够拼凑出来的最大值
  11.   for (const x of nums) {
  12.     sum += x;
  13.     // 倒着扫描
  14.     for (let j = sum; j >= x; j--) {
  15.       dp[j] |= dp[j - x];
  16.     }
  17.   }
  18.   return dp[sum / 2];
  19. };

二维数组解法

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {boolean}
  4.  */
  5. var canPartition = function (nums) {
  6.   const n = nums.length;
  7.   // n < 2，不可能将数组分割成元素和相等的两个子集，因此返回 false
  8.   if (n < 2) {
  9.     return false;
  10.   }
  12.   // 计算整个数组的元素和 sum 以及最大元素 maxNum
  13.   let sum = 0, maxNum = 0;
  14.   for (const num of nums) {
  15.     sum += num;
  16.     maxNum = maxNum > num ? maxNum : num;
  17.   }
  19.   // 如果 sum 是奇数，则不可能将数组分割成元素和相等的两个子集，因此返回 false
  20.   if (sum & 1) {
  21.     return false;
  22.   }
  24.   // 「等和子集」的和必然是总和的一半
  25.   const target = Math.floor(sum / 2);
  27.   // 如果 maxNum > target，
  28.   // 则除了 maxNum 以外的所有元素之和一定小于 target，
  29.   // 因此不可能将数组分割成元素和相等的两个子集，直接返回 false
  30.   if (maxNum > target) {
  31.     return false;
  32.   }
  34.   // 创建二维数组 dp，包含 n 行 target + 1 列
  35.   // dp[i][j] 表示从数组的 [0, i] 下标范围内选取若干个正整数（可以是 0 个），
  36.   // 是否存在一种选取方案使得被选取的正整数的和等于 j
  37.   // 初始时，dp 中的全部元素都是 false
  38.   const dp = new Array(n).fill(0).map(v => new Array(target + 1, false));
  40.   // 两种边界情况
  41.   // 1、如果不选取任何正整数，则被选取的正整数等于 0。因此对于所有 0 ≤ i < n，都有 dp[i][0]=true
  42.   for (let i = 0; i < n; i++) {
  43.     dp[i][0] = true;
  44.   }
  45.   // 2、当 i == 0 时，只有一个正整数 nums[0] 可以被选取，因此 dp[0][nums[0]]=true
  46.   dp[0][nums[0]] = true;
  48.   // 先遍历物品(数值)，再遍历背包(元素和)
  49.   for (let i = 1; i < n; i++) {
  50.     const num = nums[i];
  51.     for (let j = 1; j <= target; j++) {
  52.       // 如果 j > nums[i]，对于当前的数字 nums[i]，可以选取也可以不选取，
  53.       // 两种情况只要有一个为 true，就有 dp[i][j] 为true
  54.       if (j >= num) {
  55.         dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
  56.       } else {
  57.         // 如果 j < nums[i]，则在选取的数字的和等于 j 的情况下无法选取当前的数字 nums[i]，
  58.         // 因此有 dp[i][j]=dp[i−1][j]
  59.         dp[i][j] = dp[i - 1][j];
  60.       }
  61.     }
  62.   }
  63.   return dp[n - 1][target];
  64. };

参考阅读： https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/fen-ge-deng-he-zi-ji-by-leetcode-solution/ https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/bang-ni-ba-0-1bei-bao-xue-ge-tong-tou-by-px33/ https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/0-1-bei-bao-wen-ti-xiang-jie-zhen-dui-ben-ti-de-yo/