给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]输出: true解释: 数组可以分割成 [1, 5, 5] 和 [11].示例 2:
输入: [1, 2, 3, 5]输出: false解释: 数组不能分割成两个元素和相等的子集. 2. 分析典型的背包问题,在n个物品中选出一定物品,填满sum/2的背包 F(n, C )考虑将n个物品填满容量为C的背包 F(i,c) = F(i-1 ,c) II F(i-1 ,C- w(i) ) 时间复杂度: O(n* sum/2)= O(n* sum )
题目中给出:(1)最多有200个数字(2)每个数字最大为100。——可以得出所有数字和为20000;背包最大为10000;时间复杂度为: n * sum/2 = 100* 10000 = 100万。这个现在的计算机是可以处理的,所以算法设计合适。
题目中给出的数据规模可以帮助我们判断我们设计的算法是否是有效的合理的,每个数字的最大值是多少会对算法有影响,比如这题:最大值合在一起将决定背包的容量,进而决定算法的时间复杂度。
3. 第一种方法——记忆化搜索 第一步首先计算这些数字之和是多少:sum(nums),求出sum之后,首先必须确保sum%2=0,也就是说这个和是可以被平分的,若不能平分,我们就无法在nums中取出一部分让它等于另外一部分,因为这个和本身无法平分。 在这种情况直接return False。否则就是真正解决算法的逻辑,依旧是先使用递归+记忆化搜索:设置一个递归函数tryPartition,传入的参数包括这些数字 nums 以及这些数字的下标 len(nums)-1 以及设计的背包大小 sum//2(注意:Python3这个地方应该写为 sum//2,用地板除取整数。若写为 sum/2,当sum为奇数时会得到一个浮点类型的数,会报错)如下图: tryPartition(nums, index, sum)该函数返回的是一个bool类型的值,表示使用nums[0…index],是否可以完全填充一个容量为sum的背包。首先若发现sum=0,就说明这个背包里已经没有任何空间了,换句话说我们已经填充好了这个背包,此时应该return True。否则的话,若sum