题目
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
示例 1:
1
2
3
4
5 输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].示例 2:
1
2
3
4
5 输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
这道题与之前:
给定一个数组,每个元素加正负号使得所有元素之和等于给定的数一题,完全相同。
动态规划
只不过这道题只需要判断是否存在这样的情况,而不需要判断有多少种符合条件的情况。
仿照之前做过题的思路:如果存在一种方法使得整个集合的元素分成两个不相交的子集,使得两个子集元素和相等,那么两个子集的和必然满足:
$$
S_x=S_y=\frac{S}{2}
$$
上式中,$S_x$与$S_y$分别为两个子集的元素和,$S$为整个集合的元素和。此时问题变成动态规划问题,且是经典的0-1背包
:对于每个元素,我是否选择把它加入到集合$X$中,使得最终背包被刚好放满。
递归地解决这样一个问题,考虑如下问题:对于前$i$个元素,我们是否有可能选出一个子数组,使得子数组和为$\frac{S}{2}$,可能则为true
。
状态转移方程:
$$
dp[i][sum]=dp[i-1][sum-nums[i]]|dp[i-1][sum]
$$
其中,$dp[i][sum]$表示是否可以从前$i$个元素中选出元素和为$sum$的子数组。
1 | class Solution { |
- 时间复杂度,考虑到最差情况,数组所有元素之和最大为
200×INT_MAX
,此时时间复杂度理论上来说也为$O(N)$,但是常数项为INT_MAX
。 - 空间复杂度同上。
优化
剪枝!!当每一行的末尾为true
时,可以直接返回true
。
1 | class Solution { |
剪枝之后测试用例耗时下降一半。
总结
中间出了一些错误:忘记考虑or
不选择当前元素的情况。