分割等和子集

题目详情

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

解题思路

1. 计算数组的总和。如果总和是奇数，那么我们无法将数组分割成两个和相等的子集，因此直接返回false
2. 如果总和是偶数，那么目标就是找到一个子集，其元素和等于总和的一半
3. 定义一个二维布尔数组dp，其中dp[i][j]表示从数组的前i个元素中选取一些元素，是否可以使得这些元素的和等于j
4. 因此，对于dp[i][j]，我们有两种选择：一是选择第i个元素，那么 dp[i][j] = dp[i-1][j-nums[i]] ；二是不选择第i个元素，那么 dp[i][j] = dp[i-1][j]。所以，dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]

代码实现

var canPartition = function(nums) {
  let sum = nums.reduce((a, b) => a + b, 0)
  if (sum % 2 !== 0) return false
  let target = sum / 2
  let dp = new Array(target + 1).fill(false)
  dp[0] = true
  for (let i = 0; i < nums.length; i++) {
    for (let j = target; j >= nums[i]; j--) {
      dp[j] = dp[j] || dp[j - nums[i]]
    }
  }
  return dp[target]
};