h5网站建设价格,公司网站制作定制,建设常规的网站报价是多少钱,智能小程序WordPress题目描述
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等。注意:每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:输入: [1, 5, 11, 5]输出: true解释: 数组可以分割成 [1, 5, 5] 和 [11].示例 2:输入:…题目描述
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集使得两个子集的元素和相等。注意:每个数组中的元素不会超过 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: boollru_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)
