力扣416题：分割等和子集的动态规划详解

一、题目解读

力扣416题“分割等和子集”是一个经典的动态规划问题，要求判断给定的非空数组是否可以被分割成两个子集，使得两个子集的元素和相等。这道题实际上是“01背包问题”的变种，在算法面试中频繁出现，考察程序员对动态规划思想的理解和应用能力。

二、解题思路

本题的核心思路是将问题转化为背包问题：能否从数组中选取若干数字，使其和等于整个数组总和的一半。解题步骤如下：

1. 计算数组总和，若为奇数直接返回false

2. 确定目标和为sum/2

3. 使用动态规划数组DP，其中dp[i]表示能否组成和为i的子集

4. 采用反向遍历的方式更新dp数组，避免重复使用同一元素

5. 设置提前终止条件优化性能

三、解题步骤详解

1. 总和检查：首先计算数组总和，奇数总和无法平分

2. 初始化dp数组：创建大小为(target+1)的布尔数组，初始化dp[0]=true

3. 动态规划填充：对每个数字，从target反向遍历更新dp数组

4. 状态转移：dp[j] = dp[j] || dp[j-num]，表示当前数字是否被选用

5. 提前终止：当dp[target]为true时立即返回，优化性能

四、完整代码实现

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        // 总和为奇数直接返回false
        if (sum % 2 != 0) return false;
        
        int target = sum / 2;
        int n = nums.size();
        // dp[i]表示能否组成和为i的子集
        vector<bool> dp(target + 1, false);
        dp[0] = true; // 和为0总是可以
        
        for (int num : nums) {
            // 反向遍历避免重复使用同一元素
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
            // 提前终止条件
            if (dp[target]) return true;
        }
        
        return dp[target];
    }
};

五、总结

这道题通过将问题转化为背包问题，展示了动态规划的典型应用场景。关键点在于理解状态转移方程和反向遍历的技巧。算法时间复杂度为O(n*target)，空间复杂度为O(target)，其中n是数组长度，target是数组总和的一半。掌握此类问题对面试准备和算法能力提升大有裨益。