题目

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

  • 每个数组中的元素不会超过 100
  • 数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11]

示例 2:

输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集

方案一（动态规划，01背包问题）

  1. class Solution:
  2.     def canPartition(self, nums: List[int]) -> bool:
  3.         # 转换成01背包问题：
  4.         #   元素和为 sum, 背包大小为 sum / 2
  5.         #   求背包是否可以塞满
  6.         _sum = sum(nums)
  7.         if _sum % 2 == 1: # 奇数
  8.             return False
  10.         m = _sum // 2 # 背包大小
  11.         dp = [0] * (m + 1)
  12.         for num in nums:
  13.             for j in range(m, num - 1, -1):
  14.                 dp[j] = max(dp[j], dp[j - num] + num)
  16.         return dp[-1] == m

参考链接

https://leetcode-cn.com/problems/partition-equal-subset-sum/?utm_source=LCUS&utm_medium=ip_redirect_q_uns&utm_campaign=transfer2china