背包：数组是否可以分割两个子集，使得这两子集的元素和相等


/**
 * @description 分割等和子集, 0/1背包的变种
 * @url https://leetcode-cn.com/problems/partition-equal-subset-sum/
 * @param {number} N
 * @param {number} W
 * @param {number[]} wt
 * */
function fn(N, W, wt) {
    // :::: 初始化dp数组 及其 base case
    const dp = [];
    for (let i = 0; i <= N; i++) {
        dp[i] = [];
        for (let w = 0; w <= W; w++) {
            // ::::重量为0时，表示能够装入
            if (w === 0) {
                dp[i][w] = true;
            }
            // ::::可选择的物品为0时，表示不能装入
            else if (i === 0) {
                dp[i][w] = false;
            }
            // ::::其余情况，初始化为false
            else {
                dp[i][w] = false;
            }
        }
    }
    // ::::根据状态个数，决定嵌套层数，
    // ::::使用动态规划框架模板代码遍历
    for (let i = 1; i <= N; i++) {
        for (let w = 1; w <= W; w++) {
            // ::::剩余容量已经小于 0 了，只能取决于上一个物品的状态，是否装满了
            if (w - wt[i - 1] < 0) {
                dp[i][w] = dp[i - 1][w];
            } else {
                // ::::选择
                dp[i][w] =
                    // ::::不装入
                    dp[i - 1][w] ||
                    // ::::装入
                    dp[i - 1][w - wt[i - 1]];
            }
        }
    }
    return dp[N][W];
}


/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
    const sum = nums.reduce((a, b) => a + b, 0);
    // ::::如果总和为奇数，直接返回false
    if (sum % 2 !== 0) return false;
    // ::::背包容量
    const W = sum / 2;
    // ::::物品数量
    const N = nums.length;
    return fn(N, W, nums);
};

优化空间复杂度


var canPartition = function (nums) {
    let W = 0;
    for (let num of nums) W += num;
    // 和为奇数时，不可能划分成两个和相等的集合
    if (W % 2 !== 0) return false;
    let N = nums.length;
    W = W / 2;

    let dp = new Array(W + 1).fill(false);

    // base case
    dp[0] = true;

    for (let i = 0; i < N; i++) {
        // ::::: 从后往前遍历
        for (let w = W; w >= 0; w--) {
            if (w - nums[i] >= 0) {
                dp[w] = dp[w] || dp[w - nums[i]];
            }
        }
    }
    return dp[W];
};

时间复杂度 O(n*sum)，空间复杂度 O(sum)

注意是倒序，记住正常的解法就行，这种压缩空间复杂度的解法，还没理解透

liguwe's site

背包：数组是否可以分割两个子集，使得这两子集的元素和相等

目录

题目

题解

明确 `状态` 和 `选择`

明确 `dp数组` 的定义

定义

base case

根据 `选择` 确定 `状态转移方程`

1. 选择一：不选

2. 选择二：选择

根据 `动态规划框架` 写出 `最终代码`

优化空间复杂度