LeetCode 第416题：分割等和子集

📖 文章摘要

本文详细解析LeetCode第416题“分割等和子集”，这是一道动态规划问题。文章提供了基于0-1背包的解题思路，包含C#、Python、C++三种语言实现，配有详细的分析和性能对比。适合正在学习动态规划和背包问题的程序员。

核心知识点： 动态规划、0-1背包、数组分割
难度等级： 中等
推荐人群： 具有基础算法知识，想要深入学习动态规划的程序员

题目描述

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

示例

示例 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背包问题的变形。我们可以将其转化为：是否可以从数组中选择一些数字，使得它们的和等于整个数组和的一半。

关键点：

首先判断数组总和是否为偶数，如果是奇数则无法分割
问题转化为是否能选出一些数字，使其和为总和的一半
使用动态规划求解，dp[i][j]表示前i个数中是否可以选出和为j的子集

图解思路

动态规划状态转移表

状态	含义	计算方式	说明
dp[i][j]	前i个数能否凑出和为j	dp[i-1][j] \|\| dp[i-1][j-nums[i]]	不选或选当前数
dp[0][0]	初始状态	true	空集和为0
dp[i][0]	前i个数凑出和为0	true	都不选即可

示例分析表

输入数组	目标和	可能的划分	结果
[1,5,11,5]	11	[1,5,5] 和 [11]	true
[1,2,3,5]	5.5	无法划分	false

代码实现

C# 实现

public class Solution {
    public bool CanPartition(int[] nums) {
        int sum = nums.Sum();
        // 如果总和为奇数，无法分割
        if (sum % 2 != 0) return false;
        
        int target = sum / 2;
        int n = nums.Length;
        bool[,] dp = new bool[n + 1, target + 1];
        
        // 初始化
        for (int i = 0; i <= n; i++) {
            dp[i, 0] = true;
        }
        
        // 动态规划
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                dp[i,j] = dp[i-1,j];
                if (j >= nums[i-1]) {
                    dp[i,j] = dp[i,j] || dp[i-1,j-nums[i-1]];
                }
            }
        }
        
        return dp[n,target];
    }
}

Python 实现

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
            
        target = total // 2
        n = len(nums)
        dp = [[False] * (target + 1) for _ in range(n + 1)]
        
        # 初始化
        for i in range(n + 1):
            dp[i][0] = True
            
        # 动态规划
        for i in range(1, n + 1):
            for j in range(1, target + 1):
                dp[i][j] = dp[i-1][j]
                if j >= nums[i-1]:
                    dp[i][j] = dp[i][j] or dp[i-1][j-nums[i-1]]
                    
        return dp[n][target]

C++ 实现

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<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
        
        // 初始化
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }
        
        // 动态规划
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= nums[i-1]) {
                    dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }
        
        return dp[n][target];
    }
};

执行结果

C# 实现

执行用时：96 ms
内存消耗：39.8 MB

Python 实现

执行用时：1256 ms
内存消耗：29.6 MB

C++ 实现

执行用时：88 ms
内存消耗：9.2 MB

性能对比

语言	执行用时	内存消耗	特点
C#	96 ms	39.8 MB	性能适中，内存占用较大
Python	1256 ms	29.6 MB	执行较慢，内存占用中等
C++	88 ms	9.2 MB	执行最快，内存占用最小

代码亮点

🎯 使用二维动态规划数组清晰地表示状态转移
💡 通过预判断总和是否为偶数快速返回结果
🔍 初始化第一列（和为0的情况）优化了边界处理
🎨 三种语言实现保持了相同的算法思路，便于对比学习

常见错误分析

🚫 忘记判断数组总和是否为偶数
🚫 动态规划数组初始化不正确
🚫 状态转移方程写错，导致结果错误
🚫 没有考虑数组为空的边界情况

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
二维DP	O(n×target)	O(n×target)	思路清晰，易于理解	空间占用大
一维DP	O(n×target)	O(target)	空间占用小	不易理解和调试
DFS+剪枝	O(2^n)	O(n)	代码简单	时间复杂度高

📖 系列导航

🔥 LeetCode 题解合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第416题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

图解思路

动态规划状态转移表

示例分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流