题目描述
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路 1: DP
题目理解
一开始看到题目提到两个子数组，还有点不知道怎么跟 DP 扯上关系。
但其实题目可以换一个说法：给定数组 nums，是否存在一个子数组，该子数组的和等于 nums 元素和的一半。
这样就清晰多了。
解题
我们还是用一个一维数组 dp 来记录题目的解，dp[i] 表示是否存在元素和为 i 的子数组。
对于 nums 中的每个数字 n 来说，都有选和不选两种选择，选的话问题变成 dp[i - n]，不选的话问题还是 dp[i]，所以：
dp[i] = dp[i - n] or dp[i]
复杂度
- 时间复杂度：$O(len*target)$, len 是 nums 的长度，target 是 nums 元素和的一半。
- 空间复杂度：$O(target)$, target 是 nums 数组元素和的一半。
代码
JavaScript Code
/**
* @param {number[]} nums
* @return {boolean}
*/
var canPartition = function (nums) {
const target = nums.reduce((a, b) => a + b) / 2;
if (target % 1 !== 0) return false; // nums 和为奇数
const dp = Array(target + 1).fill(false);
dp[0] = true;
for (const n of nums) {
for (let i = target; i >= n; i--) {
// 逆向填充
if (dp[target]) return true; // 提前返回结果
dp[i] = dp[i] || dp[i - n];
}
}
return dp[target];
};
思路 2: DFS
将两个子数组 a 和 b 分别初始化为 nums 和 []，然后不断从 a 中取出数字放到 b 中，当两个子数组的和相等时，返回 true。
对于 a 中的每个数字，都有选与不选两种选择。
p.s. 要使用记忆化递归才不会超时
复杂度
- 时间复杂度：$O(2^n)$，n 为数组 nums 长度，可以看成是二叉树的遍历。
- 空间复杂度：$O(logn)$，n 为数组 nums 长度，递归栈消耗的空间。
代码
Python Code
class Solution(object):
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
@lru_cache
def dfs(i, sum1, sum2):
if sum1 == sum2: return True
if sum2 > sum1 or i >= len(nums): return False
return dfs(i + 1, sum1 - nums[i], sum2 + nums[i]) or dfs(i + 1, sum1, sum2)
total = sum(nums)
if total % 2 == 1: return False
return dfs(0, total, 0)
