LeetCode 416(分割等和子集)讲解

室长收录于找工作就像相亲和

2023-03-05 约 900 字预计阅读 2 分钟

警告

本文最后更新于 2023-03-05，文中内容可能已过时。

LeetCode 416

上一周讲了01背包问题，这周我们趁热打铁，用01背包问题的思路来解决 LeetCode 416 题。

题干简述

给定：一个只包含正整数的非空数组 nums 。

要求：判断 nums 是否可以被分割成元素和相等的两个子集。

题目详情：416. 分割等和子集

解题思路

解题的关键在于我们能否从nums中找出一些元素，「元素的和」等于「总和」的一半，如果找得到，答案即为 true，否则就是 false。
根据第 1 点，我们可以把这道题转化为01背包问题，背包容量=nums元素和/2，物品就是nums数组中的每个元素，物品的重量和价值相等，等于元素的值(也就是nums[i])。

除此之外还有一些边界条件：

首先，nums中所有元素的和必须为偶数，否则不可能被分割成元素和相等的两个子整数集。
其次，若 nums 中某个元素的值>总元素和/2，直接 return false。

图解算法

官方案例:

Input: nums = [1,5,11,5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

就像「01背包问题」这篇文章提到的那样，我们可以画出这样一个矩阵：

	1	2	3	4	5	6	7	8	9	10	11
nums[0]=1	1	1	1	1	1	1	1	1	1	1	1
nums[1]=5	1	1	1	1	5	6	6	6	6	6	6
nums[2]=11	1	1	1	1	5	6	6	6	6	6	11
nums[3]=5	1	1	1	1	5	6	6	6	6	10	11

代码实现

 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


class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        target = s // 2
        
        # 边界值检测
        if s % 2 == 1:
            return False

        # 边界值检测
        maxNum = 0
        for num in (nums):
            maxNum = max(num, maxNum)
        if maxNum > target:
            return False

        dp = [([0] * target) for p in range(len(nums))]
        # 填充矩阵第一行
        for j in range(0, target):
            subTarget = j + 1
            if subTarget >= nums[0]:
                dp[0][j] = nums[0]

        # 填充矩阵剩余所有行
        for i in range(1, len(nums)):
            num = nums[i]
            for j in range(0, target):
                subTarget = j + 1
                if subTarget > num:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-num]+num)
                elif subTarget == num:
                    dp[i][j] = num
                else:
                    dp[i][j] = dp[i - 1][j]
            if dp[i][target-1] == target:
                return True

        return False

复杂度

时间复杂度O($n^2$)，空间复杂度O($n^2$)，在 LeetCode 上面的表现并不理想：

/leetcode/dp-leetcode-416/1.png

网上还是有不少优化方案的，比如将二维数组优化为一维数组，空间复杂度从O($n^2$)降到O(n)。

不过这篇文章的本意在于利用上一篇「01背包问题」学到的东西来解决 LeetCode 中相关的题目，所以先不展开讲了，以后有机会再讨论这个话题。

Buy me a coffee~

赞赏

支付宝

微信