[100天算法】-分割等和子集（day 78）

题目描述

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。注意:每个数组中的元素不会超过 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_cachedef dfs(i, sum1, sum2):if sum1 == sum2: return Trueif sum2 > sum1 or i >= len(nums): return Falsereturn dfs(i + 1, sum1 - nums[i], sum2 + nums[i]) or dfs(i + 1, sum1, sum2)total = sum(nums)if total % 2 == 1: return Falsereturn dfs(0, total, 0)