分割等合子集

题目

https:leetcode.cn/problems/partition-equal-subset-sum/description/?envType=daily-question&envId=2025-04-07

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

实现

分析

思路：典型 01 背包问题，动态规划 问题转化：是否存在字符组元素和为 sum/2 dp 定义：dp[i][j] 表示前 i 个元素能否和第 j 个元素组成满足条件的子数组 状态转移:

• 不选当前数: dp[i][j] = dp[i-1][j]
• 选当前数: dp[i][j] = dp[i-1][j-nums[i]] 注意：sum/2 为奇数时直接返回 false 复杂度：
• 时间复杂度：$O(n\ast target)$
• 空间复杂度：$O(target)$

/**
 * @param {string} s
 * @return {string}
 */
var canPartition = function (nums) {
    const sum = nums.reduce((a, b) => a + b, 0);
    if (sum % 2 !== 0) return false;
 
    const target = sum / 2;
    const dp = 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];
};