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. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网