Keshawn_lu's Blog

Leetcode 416. 分割等和子集

字数统计: 685阅读时长: 3 min
2020/10/11 Share

题目简介:

给定一个只包含正整数非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

注意:

  1. 每个数组中的元素不会超过 100
  2. 数组的大小不会超过 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

解释: 数组不能分割成两个元素和相等的子集.

思路:

我们记所有元素的和为sum,由于sum为奇数时,无法分成两个相同的和,所以直接返回false

sum为偶数时,我们需要知道是否能找到一种选数字的方案,使其和等于sum / 2,则剩余的数字和也为sum / 2

这时我们可以使用动态规划,dp[i][j]代表在nums[0...i]中,是否可以选出一种方案(可以不选数字),使其和为j

我们先考虑边界情况:

  • dp[i][0] = true(不选数字,和就为0)
  • dp[0][nums[0]] = true

由于数组中都为正数,所以可以分为两种情况讨论:

  • j - nums[i] < 0时,说明之前的i - 1个数存在和为负数的方案,由于不可能存在该情况,所以不能选这个数字,则dp[i][j] = dp[i - 1][j]
  • j - nums[i] >= 0时,选不选这个数字都可以,则dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]。(注意都是i - 1,当前i - 1个数字可以选择出j - nums[i]的和时,加上nums[i],则和为j)

最后返回dp[nums.size() - 1][sum]即可。

tip:

  • 我们还需要找出数组中最大的数字,若该数字大于sum / 2,则必不可能存在方案,直接返回false即可。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:

bool canPartition(vector<int>& nums) {

int sum = 0;
int maxnum = INT_MIN;

for(int i = 0; i < nums.size(); i++){

sum += nums[i];
maxnum = max(maxnum, nums[i]);
}

if(sum % 2 == 1) //奇数不可能分成两个相同的子集
return false;

sum = sum / 2;
if(maxnum > sum)
return false;

//dp[i][j]
//nums[0....i],中能否选出一种方案,使其和为j
vector<vector<bool>> dp(nums.size(), vector<bool>(sum + 1, false));

for(int i = 0; i < nums.size(); i++){

dp[i][0] = true; //什么都不选,和就为0
}
dp[0][nums[0]] = true;

for(int i = 1; i < nums.size(); i++){

for(int j = 1; j <= sum; j++){

if(j - nums[i] < 0){ //说明不能选这个数字

dp[i][j] = dp[i - 1][j];
}
else //既可以选,也可以不选
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]; //注意都是 i - 1
}
}

return dp[nums.size() - 1][sum];
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: