LeetCode 416题解法：分割等和子集的动态规划解析（附C++代码）

一、题目解读

LeetCode 416题“分割等和子集”要求判断一个整数数组能否被分成两个元素和相等的子集。例如，数组[1,5,11,5]可以分成[1,5,5]和[11]，返回true；而[1,2,3]无法等分，返回false。问题本质是子集求和的变种，需判断是否存在子集使其和等于数组总和的一半。

二、解题思路

采用动态规划解决。核心思想是构建一个布尔型dp数组，dp[i]表示能否用原数组元素组成和为i的子集。关键在于状态转移方程：若当前元素num加入子集后，剩余元素能组成目标值target-num，则dp[target]为真。为避免重复使用元素，内层循环需反向遍历。

三、解题步骤

1. 计算数组元素总和sum，若为奇数直接返回false（无法等分）。

2. 定义目标值target = sum/2，初始化dp[0]=true（空子集和为0）。

3. 外层循环遍历每个元素num，内层从target反向遍历至num：

    若dp[j]（j为目标值）或dp[j-num]为真，更新dp[j] = true。

    若提前发现dp[target] = true，立即终止循环返回true。

4. 最终返回dp[target]的结果。

四、代码与注释

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0); // 计算总和
        if (sum % 2!= 0) return false; // 奇数和无法等分

        int target = sum / 2; // 目标值
        int n = nums.size();
        vector<bool> dp(target + 1, false); // dp[i]：能否组成和为i的子集
        dp[0] = true; // 和为0的子集始终存在

        for (int num : nums) { // 遍历每个元素
            for (int j = target; j >= num; j--) { // 反向遍历避免重复使用元素
                dp[j] = dp[j] || dp[j - num]; // 状态转移：若j或j-num可达，则j可达
            }
            if (dp[target]) return true; // 提前终止条件
        }
        return dp[target];
    }
};

注释解析：

● accumulate函数简化了总和计算，奇偶判断为关键剪枝条件。

● 反向循环保证每个num仅被使用一次，避免组合重复。

● 提前终止优化减少无效遍历，提升效率。

五、总结

动态规划通过状态压缩将子集问题转化为线性求解，时间复杂度O(n*target)，空间复杂度O(target)。代码利用奇偶剪枝和提前终止进一步优化性能，是解决此类问题的经典范式。掌握动态规划的核心逻辑（状态定义、转移方程、边界条件）对解决背包问题、组合问题等具有重要意义。