逆天，好不容易找到的工作，学校不让去实习。。。

专栏：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算法文档 。