【DP、Greedy+DFS】416. Partition Eq
问题描述：
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：使用贪心算法求解（错误思想，但是竟然 AC 了）：
- 先对所有数进行从大到小排序；
- 使用双指针 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。
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
虽然可以 AC，但是之后有人告诉我实际上这种贪心的思想是错误的，比如考虑：[23,13,11,7,6,5,5]，应该返回 True（[23,7,5] 和 [13,11,6,5]），但是按照上述代码的思想，会返回 False。竟然发现了 Leetcode 的一个 bug，哈哈哈~
方法2：使用动态规划求解（正确思想）：
实际上，这道题是01-背包问题的应用：01-背包、完全背包、多重背包及其相关应用。
我们可以将问题转化为以下的形式：是否有一个子数组的元素之和，恰好等于原数组元素之和的一半呢？而对于原数组中的每一个元素，都有两种状态：在子数组里面或者不在子数组里面（先假设存在这个子数组）。这样一看，我们就能发现这个问题与0-1背包问题非常相似，因此我们可以采用0-1背包问题的解法去解决这道问题。
在这道题目中，原数组里面的每个元素都可以看作是一种物品，而这件物品的重量和价值都为元素值；原数组的和的一半可看作背包的最大承重量，而当背包能放下物品的最大价值为原数组和的一半时，就返回真，否则返回假。
因此，我们就能很容易的得到以下算法：
- 在这个问题中，背包容量为数组和的一半，因此需要
dp[len(nums)+1][sum(nums)//2+1]大小的数组，其中dp[i][j]表示前 i 个数放入容量为 j 的背包中的目标值； - 如果 j 小于当前第 i 个数的容量，即 j < nums[i-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-背包的思想和解法进行解决。如果每件物品可以放若干件，那就变成多重背包问题了。
方法3：使用贪心 + DFS回溯法求解（beats 100%）：
其实这道题和 Leetcode 【Greedy+DFS】473. Matchsticks to Square 以及 Leetcode 【Greedy+DFS】698. Partition to K Equal Sum Subsets 几乎一模一样，只需要将 Leetcode 473 中的 4 改成 2 即可。
Python3 实现：
class Solution:
def canPartition(self, nums: List[int]) -> bool:
def search(ind): # ind为nums下标，从0开始
if ind == N: # 将nums全部数填入targets，返回True
return True
for i in range(2): # 对于每一个targets
if targets[i] >= nums[ind]: # 保证targets该位置的数字>=放置的数字
targets[i] -= nums[ind]
if search(ind + 1):
return True
targets[i] += nums[ind] # 回溯
return False
div, mod = divmod(sum(nums), 2)
if mod != 0:
return False
nums.sort(reverse=True) # 降序排序可以减少递归次数(亲测)
if not nums or nums[0] > div: # 数组可能为空
return False
N = len(nums)
targets = [div] * 2 # 2个大小为目标数的桶
return search(0)
这个代码运行只有 36ms，远远好于上述两种方法，beats 100% 的提交。
