416. Partition Equal Subset Sum

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @return {boolean}
 */

题目给我们一个数字数组 nums

要求我们求出是否能将 nums 分成两个和相等的数组

解题思路

题目要求把 nums 分成两个数组，且两个数组的和相等，所以这间接告诉我们，这两个数组的和必须是 nums 所有元素和的一半

于是我们的目标变成了，从 nums 中找元素组成一个新数组（元素不可重复），其数组元素之和为 nums 所有元素和的一半

至此，这题有点类似 322，区别在于 322 的硬币可以用多个，而我们数组元素只能用一次

处理方法还是类似，我们使用一个数组 dp 来保存可以凑出来的数字

由于我们的目标是凑出 target（ target = sum(...nums)/2），所以我们只需要一个长度为 target+1 的 dp 即可

初始值：dp[0] = true 代表数字 0 我们一定能凑出来（因为不需要任何 nums 的元素）

接下来我们需要遍历 nums，找出所有可以被凑出来的数字，如果最后 target 可以被凑出来我们就返回 true；否则返回 false

对于每一个 nums 中的 num，我们需要倒序遍历 dp（因为如果正序遍历的话我们会使用多次同一个 num）

此时有两种情况：

1. dp[i] === true 代表当前数字已经可以被凑出来，我们直接 continue
2. dp[i-num] === true 代表在 num 出现之前数字 i-num 可以被凑出来，那么此时我们需要把 dp[i] = true（因为此时我们有 num 了，如果 i-num 可以被凑出来，i 也可以被凑出来）

循环终止条件就是 dp[target] === true 或者循环结束

Javascript

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
    const total = nums.reduce((acc, cur) => acc + cur, 0)
    // if the total is odd, it cannot be split in half
    if (total % 2 === 1) {
        return false
    }

    // now we only have to find a subset which sum(subset) = total/2
    const target = total / 2
    // if dp[i] === true, means we can find a subset which sum(subset) === i
    const dp = new Array(target + 1).fill(false)
    dp[0] = true
    for (const num of nums) {
        for (let i = target; i >= num; i--) {
            // if the i is already reachable, just continue
            if(dp[i]) {
                continue
            }
            // if i-num was reachable, and we have num now, so i is reachable now
            if(dp[i - num]) {
                dp[i] = true
            }
            // avoid unnecessary calculations
            if(dp[target]) {
                return true
            }
        }
    }
    return false
};