个人备案公司网站,谈谈网站建设创新问题,海南网站seo,四平seo给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等。
示例 1#xff1a; 输入#xff1a;nums [1,5,11,5] 输出#xff1a;true 解释#xff1a;数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2使得两个子集的元素和相等。
示例 1 输入nums [1,5,11,5] 输出true 解释数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2 输入nums [1,2,3,5] 输出false 解释数组不能分割成两个元素和相等的子集。
提示
1 nums.length 200 1 nums[i] 100 题目链接 思路定义 dp[i][j] 表示从 nums 中前 i 个元素挑选若干个数是否存在和为 j 的可能 dp[i][0] 1 显然 dp[i][j] dp[i-1][j] or (dp[i-1][j-nums[i]] if jnums[i] else 0)时间复杂度为 O(n*sum(nums)/2)
class Solution:def canPartition(self, nums: List[int]) - bool:totalSum sum(nums)if totalSum%21 or len(nums)1:return Falsetarget int(totalSum/2)## dp[i][j] nums 中前 i 个数存在相加和为 jdp [[0 for j in range(target1)] for i in range(len(nums))]for i in range(len(nums)):dp[i][0] 1for i in range(1, len(nums)):for j in range(1, target1):if dp[i-1][j] 1:dp[i][j] 1if j nums[i] and dp[i-1][j-nums[i]]1:dp[i][j] 1if j target and dp[i][j] 1:return Truereturn False
