LCR 101. 分割等和子集

给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。

示例 1：

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

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：nums 不可以分为和相等的两部分

提示：

• 1 <= nums.length <= 200

• 1 <= nums[i] <= 100

思路

• 递归+回溯

  • 时间复杂度：≈O(2^k)

    • 近似最坏时间复杂度为 O(2^n)，其中 n 是可选数字种类数

  • 空间复杂度：=O(sum)

    • counts[101] 是常数空间

    • 递归调用栈最多深度为 O(sum)（和的最大值为 100*200=20000，实际因剪枝大大减少）

• 动态规划

  • 时间复杂度：≈ O(n * target)

    • 其中 n 是不同数字种类数量（最多 100），target = sum / 2。

  • 空间复杂度：= O(target)

    • boolean[] dp = new boolean[target + 1]

    • oldDp = dp.clone()

代码

• 递归+回溯

class Solution {
    //LCR 101. 分割等和子集
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int[] counts = new int[101];
        for (int num : nums) {
            sum += num;
            counts[num]++;
        }
        if ((sum & 1) == 0) {//等和判断：两个等和子集的总和一定为偶数
            sum >>= 1;
            //获取最大可用数
            int index = 100;
            if (sum < index) {
                index = sum;
            }
            //开始回溯
            return judge(counts, index, sum);
        }
        return false;
    }

    private boolean judge(int[] counts, int index, int sum) {
        //找到当前最大可用数字
        while (sum < index || (0 < index && counts[index] == 0)) {
            index--;
        }
        //没有可用数
        if (index == 0) {
            return false;
        }
        sum -= index;
        if (sum == 0) {
            return true;
        }
        counts[index]--;
        //减去后回溯
        if (judge(counts, index, sum)) {
            return true;
        }
        //回溯失败则退回当前可用数，并将当前可用数排除
        sum += index;
        index--;
        //继续回溯
        return judge(counts, index, sum);
    }
}

• 动态规划

class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        if ((totalSum & 1) == 1) { // 总和为奇数，不可能分割
            return false;
        }
        int target = totalSum / 2; // 目标和
        
        boolean[] dp = new boolean[target + 1];
        dp[0] = true; // 初始状态：和为0可达
        
        // 统计数字频率（只考虑 <= target 的数字）
        int[] counts = new int[101];
        for (int num : nums) {
            if (num <= target) {
                counts[num]++;
            }
        }
        
        // 动态规划：处理每个数字
        for (int num = 1; num <= 100; num++) {
            if (counts[num] == 0) continue; // 跳过未出现的数字
            
            boolean[] oldDp = dp.clone(); // 保存当前状态
            dp = new boolean[target + 1]; // 新状态数组
            
            // 对每个余数 r (0 到 num-1) 使用滑动窗口
            for (int r = 0; r < num; r++) {
                int trueCount = 0; // 窗口中 true 的数量
                for (int i = 0; ; i++) {
                    int j = r + i * num; // 当前和 j
                    if (j > target) break;
                    
                    // 新状态：可达如果旧状态可达 或 窗口中有 true（使用当前数字）
                    dp[j] = oldDp[j] || (trueCount > 0);
                    
                    // 将 oldDp[j] 加入窗口
                    if (oldDp[j]) {
                        trueCount++;
                    }
                    
                    // 移除超出窗口大小的元素（窗口大小 = counts[num]）
                    if (i >= counts[num]) {
                        int removeIndex = r + (i - counts[num]) * num;
                        if (oldDp[removeIndex]) {
                            trueCount--;
                        }
                    }
                }
            }
        }
        return dp[target];
    }
}