Leetcode 416. 分割等和子集
2023-04-07 本文已影响0人
尹学姐
题目要求
给你一个 只包含正整数 的 非空 数组 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
解题思路
本质是从数组中选取一些数,使得其和为target
,其中target=sum/2
。
很明显,这是一道0-1
背包的题目,用动态规划来解题,下面我们来找一下动态规划的递推公式和起始值。
定义dp数组:
boolean[][] dp[i][j]
:由前i个数字,能否组成合为j的值
递推公式:
- 如果
j >= nums[i]
:dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]]
-
dp[i-1][j]
对应不选当前nums[i]
到背包 -
dp[i-1][j-nums[i]]
对应选当前nums[i]
到背包
-
- 如果
j < nums[i]
:dp[i][j] = dp[i-1][j]
- 超过背包的容量,肯定不能选
起始值:
dp[i][0] = true
:由i
个数字,组成和为0
,永远为true
,因为只需要所有数字都不选即可
Java代码
class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length;
int sum = 0;
for(int num : nums){
sum += num;
}
if(sum % 2 != 0) return false;
int target = sum / 2;
// 前i个数组成合为j
boolean[][] dp = new boolean[n+1][target+1];
for(int i = 0; i <= n; i++){
dp[i][0] = true;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= target; j++){
if(j < nums[i-1]){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i-1]];
}
}
}
return dp[n][target];
}
}
因为整个递推公式,dp[i][j] 只与它前面的值有关,所以我们可以优化空间为一维,并且改成从后往前遍历。
优化空间复杂度后:
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for(int num : nums){
sum += num;
}
if(sum % 2 != 0) return false;
int target = sum / 2;
boolean[] dp = new boolean[target+1];
dp[0] = true;
for(int i = 0; i < nums.length; i++){
for(int j = target; j >= nums[i]; j--){
dp[j] |= dp[j - nums[i]];
}
}
return dp[target];
}
}
总结
这道题通过变形之后,可以变成一个典型的0-1背包的题目,用动态规划来解决。
值得注意的是,我们给出了优化空间复杂度之后的解法,注意需要将j从后往前遍历,否则会被覆盖,导致错误的结果。