专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
最近一网友发文称，大四没课想请假去实习，结果学校不批，引来其他网友的各种吐槽。其实我对这件事也不能理解，我认为大四就是应该去找工作，去实习的，如果没课还留在学校干啥呢？
记得十多年前我大四的时候，同学基本上都快跑光了，走的时候也没和任何人说，毕业答辩的时候回来就行了。如果他直接走，不和学校说估计会好一些，但每个学校的制度又不太一样，有的管的严，有的管的松，不能一概而论。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第416题：分割等和子集。
问题描述
来源：LeetCode第416题
难度：中等
给你一个只包含正整数的非空数组 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
问题分析
这题是让判断能不能把数组分成两部分，并且这两部分的和都相等。其实这是一道典型的01背包问题，关于 01背包，完全背包和多重背包，以及它们的公式推导和状态压缩 ，我们在 中都有过详细讲解，这里就不在重复介绍。
我们来看下这题使用01背包该怎么解，首先要计算数组中所有元素的和sum，这个和必须是偶数，数组才 有可能 被分成相等的两部分，否则没法分，并且每一部分的值都是sum/2。那么这题就变成了从数组中选择一些数字，每个数字最多只能选择一次，判断它们的和是否等于sum/2，这就是01背包问题了。
关于01背包的详细介绍可以看下中的第11章动态规划部分，下面我们使用的是状态压缩后的代码，要注意第二个for循环一定要逆序。还有这两个for循环的位置不能调换，因为背包问题实际上是一个组合问题。
JAVA：
public boolean canPartition(int[] nums) { int sum = 0;// 计算所有数字的和 for (int num : nums) sum += num; if ((sum & 1) == 1)// 如果和是奇数，不能分为两部分 return false; // 转化为01背包问题，从数组中选择一些数字， // 判断他们的和是否等于target。 int target = sum >> 1; boolean[] dp = new boolean[target + 1]; dp[0] = true; // 对于01背包的优化这里是先遍历物品在遍历容量，但要注意第二个 // for循环一定要逆序。 for (int num : nums) { for (int i = target; i > 0; i--)// 这里一定要逆序 if (i >= num) dp[i] = dp[i] || dp[i - num]; } return dp[target]; }C++：
public: bool canPartition(vector
&nums) { int sum = 0;// 计算所有数字的和 for (auto &num: nums) sum += num; if (sum & 1)// 如果和是奇数，不能分为两部分 return false; // 转化为01背包问题，从数组中选择一些数字， // 判断他们的和是否等于target。 int target = sum >> 1; vector
dp(target + 1, 0); dp[0] = true; // 对于01背包的优化这里是先遍历物品在遍历容量，但要注意第二个 // for循环一定要逆序。 for (auto &num: nums) { for (int i = target; i > 0; i--)// 这里一定要逆序 if (i >= num) dp[i] = dp[i] || dp[i - num]; } return dp[target]; }
Python：
def canPartition(self, nums: List[int]) -> bool: sums = sum(nums) # 计算所有数字的和 if sums % 2: # 如果和是奇数，不能分为两部分 return False ''' 转化为01背包问题，从数组中选择一些数字， 判断他们的和是否等于target。 ''' target = sums // 2 dp = [True] + [False] * target ''' 对于01背包的优化这里是先遍历物品在遍历容量，但要注意第二个 for循环一定要逆序。 ''' for i, num in enumerate(nums): for j in range(target, num - 1, -1): # 这里一定要逆序 dp[j] |= dp[j - num] return dp[target]笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。