题目来源
题目详情
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入： nums = [1,5,11,5]
输出： true
解释： 数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入： nums = [1,2,3,5]
输出： false
解释： 数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
题解分析
解法一：动态规划
- 本题最直观的解题思路就是，先对整个数组求和，如果数组不能整除，那么肯定不能划分为两个子集；
- 此外，如果数组元素和可以被整除，但是数组中有元素的值大于元素和的一半，那么也一定无法划分为两个子集。
- 当求出了元素和，且除以2之后得到ave，本题其实可以转换为：数组中是否可以找到一些元素，使之恰好组成ave。
- 再仔细思考上面这个分析，细心的同学可能可以发现，这和0-1背包问题有些类似，因为0-1背包问题最原始的问题是从前i个物品中选择一些价值最大的，但是重量不超过背包重量的元素。这题也可以转换为0-1背包问题，因为这些元素最多只能被选中一次。
- 我们设定一个状态转移方程：\(boolean dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]]\)。需要注意的是，我们的\(dp[i][j]\)被表示为：前i个元素中，是否有一些元素可以形成元素和恰好为j。此外，这里的转移方程表示为，不选择当前元素，前i-1个元素是否可以形成和为j，或者选择当前元素的话是否可以形成和为j。
- 需要注意的是，在遍历的过程中，不能忽略当j<nums[i]的情况，这种状态也是需要根据前面的状态进行转移的：即\(dp[i][j] = dp[i-1][j]\)。
- 最后，就是关于边界值的设置了，当j为0时，我们可以看成是从前i个元素选择一些元素和为0的可能性，这当然是可能的，因为我们可以选择0个元素，所以我们将\(dp[i][0]\)设置为true。那可能有的人会问，那当i为0时为什么不设置为true呢？这是因为0个元素不能构造成任何元素和，所以设置为false。
class Solution {
public boolean canPartition(int[] nums) {
// 求和 -》求平均值 -》如果不能整除那必然不能分割 -》如果数组中有元素的值大于平均值，也不能分割
int n = nums.length;
int sum = 0;
int max = 0;
for(int i=0; i<n; i++){
sum += nums[i];
max = Math.max(max, nums[i]);
}
if((sum & 1) == 1){// 是奇数直接返回false
return false;
}
int ave = sum >> 1;
if(max > ave){// 数组中的最大值大于平均值也直接返回false
return false;
}
boolean[][] dp = new boolean[n+1][ave + 1];// dp[i][j]表示前i个数是否能组成j
// dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]]
for(int i=0; i<n; i++){
dp[i][0] = true;
}
for(int i=1; i<=n; i++){
for(int j = 0; j<=ave; j++){
if(j >= nums[i-1]){
dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i-1]];
}else{
dp[i][j] = dp[i-1][j];
}
}
}
return dp[n-1][ave];
}
}
解法二：动态规划压缩数组
- 还是前面说到的，这是一道动态规划的题目，一旦涉及到动态规划，我们就应该时刻牢记，是否可以使用压缩数组对空间进行压缩呢？
- 针对本题来说，这里是可以使用压缩数组进行压缩的，因为当前状态只依赖于前一个状态。需要注意的是，与传统的0-1背包一样，在遍历第二维的时候，需要使用倒序，因为只有当倒遍历的时候，\(dp[i-nums[i]]\)才能表示的是上一轮的dp状态。
- 此外，对于初始状态或者边界值的设定来说，这里只需要设置dp[0]为true即可。
class Solution {
public boolean canPartition(int[] nums) {
// 求和 -》求平均值 -》如果不能整除那必然不能分割 -》如果数组中有元素的值大于平均值，也不能分割
int n = nums.length;
int sum = 0;
int max = 0;
for(int i=0; i<n; i++){
sum += nums[i];
max = Math.max(max, nums[i]);
}
if((sum & 1) == 1){// 是奇数直接返回false
return false;
}
int ave = sum >> 1;
if(max > ave){// 数组中的最大值大于平均值也直接返回false
return false;
}
boolean[] dp = new boolean[ave + 1];// dp[i][j]表示前i个数是否能组成j
// dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]]
dp[0] = true;
for(int i=1; i<=n; i++){
for(int j = ave; j >= nums[i-1]; j--){
dp[j] = dp[j] | dp[j-nums[i-1]];
}
}
return dp[ave];
}
}