描述给定一个只包含正整数的非空数组，找出是否可以将该数组分成两个子集，使得两个子集中的元素之和相等。注意：每个数组元素不会超过100。数组大小不会超过200。示例1：输入：[1,5,11,5]输出：true解释：数组可以划分为[1,5,5]and[11].Example2:Input:[1,2,3,5]Output:falseExplanation:数组不能被划分为相等和的子集。描述给定一个只包含正整数的非空数组。是否可以将此数组拆分为两个子集，使两个子集的元素之和相等。注意：每个数组中的元素不会超过100数组的大小不会超过200示例1：输入：[1,5,11,5]输出：true解释：数组可以分为[1,5,5]和[11]。示例2：输入：[1,2,3,5]输出：false解释：数组不能分成两个元素和相等的子集。来源：LeetCode链接：https://leetcode-cn.com/probl...版权归灵口网所有。商业转载请联系官方授权，非商业转载请注明出处。思路本题属于背包问题。给定一个数组，将数组中的数分成两组，使两组数组的和相等，相当于：在整个数组中，每个数只能使用一次，找到这样的数使得这些数字的总和是整个数组总和的一半。即候选集是一个数组，袋子的大小是数组之和的一半。首先可以直接排除两个和一定不相等的情况。对于一个数组num，我们记下num的两个子数组之和为x，x+x=sum(num)，所以num的和一定是偶数。那么如果整个num的和是奇数，我们直接返回False；子数组之和为x，则数组num的最大值必须小于等于x，如果最大值大于x（即num之和的一半），我们直接返回假；我们把数组从小到大排序，动态规划，状态：dp[i][j]表示是否可以用num的第i个（索引，包括i）做和j，传递方程，对于dp[i][j]，我们已经知道了dp[i-1]的所有情况，如果dp[i-1][j]为真，那么不用第i个数就可以得到和j，如果dp[i-1][j]为False，那么我们检查dp[i-1][j-num[i]]是否为真，这意味着我们使用第i个数字num[i]，如果第i-1个数如果j-nums[i]可以组成，我们可以用前i个数来求和j。传递方程为：dp[i][j]=dp[i-1][j]ifdp[i-1][j]elsedpi-1]你可以参考这个视频。#-*-coding:utf-8-*-#@Author:何睿#@CreateDate:2019-10-2609:30:29#@LastModifiedby:何睿#@LastModifiedtime:2019-10-2610:18:19输入importListclass解决方案：defcanPartition(self,nums:List[int])->bool:sum_nums=sum(nums)ifsum_nums&1ormax(nums)>(sum_nums>>1):returnhalf_sum=sum_nums>>1nums.sort(reverse=True)dp=[[False]*(half_sum+1)for_inrange(2)]dp[0][0]=Truedp[0][nums[0]]=Trueforiinrange(1,len(nums)):idx=i%2forjinrange(nums[i]):dp[idx][j]=dp[idx-1][j]forjinrange(nums[i],half_sum+1):dp[idx][j]=dp[idx-1][j]ifdp[idx-1][j]elsedp[idx-1][j-nums[i]]ifdp[idx][-1]:returnTruereturndp[-1][-1]源码文件在这里。?
