[LeetCode] 每日一题 416. 分割等和子集（记忆化搜索）

题目描述

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

题目链接

https://leetcode.cn/problems/partition-equal-subset-sum

示例输入

示例 1

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

示例 2

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示

• 1 <= nums.length <= 200

• 1 <= nums[i] <= 100

解题思路

今天这题和昨天的题目确实有些相似，依然可以通过 记忆化搜索 来解决。不过区别在于，这题我们可以借助 背包问题的思路 来建模。我们设目标为整个数组和的一半，问题就转化成了：是否可以从数组中选出若干个数，使它们的和恰好等于这个目标值。

这是一个经典的 0-1 背包问题，每个数要么选，要么不选，因此在搜索过程中我们需要记忆两个维度的状态：

• 当前处理的数字下标 index

• 当前剩余的目标值 target

我们构造一个二维记忆数组 memory[index][target]，状态值有三种含义：

• 0 表示未计算

• 1 表示该状态下可以找到满足条件的子集

• -1 表示该状态下无法找到满足条件的子集

用这种方式可以有效避免重复计算，提升效率。在代码实现时，我选择了先排序数组（虽然这不是必要的，但可以让剪枝更早生效），并在搜索中尽早返回。思路上其实也挺有意思的，某种程度上是在 “穷举 + 剪枝 + 记忆化” 中找到平衡

class Solution {
    public boolean canPartition(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        // 0 表示未计算，1 表示可以满足需求，-1 表示无法满足需求
        int[][] memory = new int[nums.length][target + 1];
        return dfs(0, target, nums, memory);
    }

    private boolean dfs(int index, int target, int[] nums, int[][] memory) {
        if (index >= nums.length) {
            return target == 0;
        }
        if (memory[index][target] != 0) {
            return memory[index][target] == 1;
        }
        if (target < nums[index]) {
            return false;
        }
        boolean ans = dfs(index + 1, target, nums, memory) || dfs(index + 1, target - nums[index], nums, memory);
        memory[index][target] = ans ? 1 : -1;
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n * target)，其中 n 是数组长度，target 是数组总和的一半（也就是背包容量）。每个状态最多只会被计算一次 ✨

• 空间复杂度：O(n * target)，用于存储记忆数组 memory 🧠

总结

这题让我再次感受到记忆化搜索的强大，尤其是在背包模型这种经典问题上。虽然看似是简单的加减组合，但当状态空间被有效压缩之后，性能提升非常明显。

同时也加深了我对“背包问题建模”这种通用解题套路的理解。很多看起来是组合选择的问题，其实都可以转化成“能否填满一个背包”。这类问题不仅能用搜索做，也能用 DP 优化，甚至空间还能再压一压，有时间可以再继续尝试不同做法 👀

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。