【DP、Greedy】416. Partition Equal Subset Sum

问题描述：

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

• Each of the array element will not exceed 100.
• The array size will not exceed 200.

Example 1:

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

Example 2:

Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

解题思路：

划分成相等的子集和，容易得到以下性质：

• 如果只有一个数，则肯定不能划分；
• 如果所有数和为奇数，则肯定不能划分；
• 划分的目标是所有数总和除以2。

方法1：使用贪心算法求解：

• 先对所有数进行从大到小排序；
• 使用双指针 i，j；i 指向当前数字，j 向后移动；
• 双循环，外层循环 i 每次指向一个数字，内层循环 j 在移动的过程中： 1、如果当前累加和 < 目标，则更新累加和； 2、如果累积和 == 目标，则返回 True； 3、如果累加和 > 目标，则什么都不做。
• 最后，如果不能划分，返回 False。

例如：nums = 10,8,7,6,5,4，第一次循环，i 指向 10，j 在遍历的过程中，10 和 8 可以装进去，但是后面的数字不行；第二次循环，i 指向 8，j 在遍历的过程中，8、7 和 5 可以装进去，并且正好等于 20，则返回 True。

注意： 必须从大到小排序，因为我们使用的是一种贪心的策略：每次先装大的，再装次大的。如果次大的装入超过了目标，则会继续向后挑选第三大、第四大...，这样是可行的。但是，如果不排序，如 nums = 4,5,6,7,8,10，采取上述方法会返回 False。

时间复杂度为 O(n^2)，空间复杂度为 O(1)。

Python3 实现如下：

class Solution:
    def canPartition(self, nums):
        lens = len(nums)
        if lens == 1:
            return False
        tot = sum(nums)
        if tot % 2 == 1:
            return False
        target = tot // 2
        nums.sort(reverse=True)  # 从大到小排序
        for i in range(lens):
            tem = 0
            for j in range(i, lens):
                if tem + nums[j] == target:
                    return True
                elif tem + nums[j] < target:
                    tem += nums[j]
        return False

print(Solution().canPartition([6,5,4,8,10,7]))  # True

方法2：使用动态规划求解：

实际上，这道题是01-背包问题的应用：01-背包问题及其应用。

我们可以将问题转化为以下的形式：是否有一个子数组的元素之和，恰好等于原数组元素之和的一半呢？而对于原数组中的每一个元素，都有两种状态：在子数组里面或者不在子数组里面（先假设存在这个子数组）。这样一看，我们就能发现这个问题与0-1背包问题非常相似，因此我们可以采用0-1背包问题的解法去解决这道问题。

在这道题目中，原数组里面的每个元素都可以看作是一种物品，而这件物品的重量和价值都为元素值；原数组的和的一半可看作背包的最大承重量，而当背包能放下物品的最大价值为原数组和的一半时，就返回真，否则返回假。

因此，我们就能很容易的得到以下算法：

• 在这个问题中，背包容量为数组和的一半，因此需要 dp[len(nums)+1][sum(nums)//2+1] 大小的数组，其中 dp[i][j] 表示前 i 个数放入容量为 j 的背包中的目标值；
• 如果 j 小于当前第 i 个数的容量，即 j < numsi-1，则 dp[i][j] = dp[i-1][j]；
• 否则，dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i-1]] + nums[i-1])；
• 在每填完表的一行时，就应该判断一下是否达到了目标值，即 dp[i][j] 是否为 True，而不是等更新完表的所有行再判断；
• 如果更新完所有行，dp[-1][-1] 不等于目标值，则说明不能划分，返回 False。

时间复杂度为 O(n^2)，空间复杂度为 O(n*(sum(nums) // 2))。

Python3 实现：

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        lens = len(nums)
        if lens == 1:
            return False
        tot = sum(nums)
        if tot % 2 == 1:
            return False
        tar = tot // 2
        dp = [[0] * (tar+1) for _ in range(lens+1)]
        for i in range(1, lens + 1):
            for j in range(1, tar + 1):
                if j < nums[i-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i-1]] + nums[i-1])
            if dp[i][j] == tar:  # 更新完一行就应该判断一下
                return True
        return False

print(Solution().canPartition([2,5,3,4]))  # True
print(Solution().canPartition([5,1,3,5]))  # False

注：这类题目，即物品（数组元素）有存在与否两种状态的题目，都可以用01-背包的思想和解法进行解决。