```python class Solution: # 一个 只包含正整数 的 非空 数组 nums 。 # 请判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 def canPartition(self, nums: List[int]) -> bool: total = 0 for v in nums: total += v if total % 2 == 1: return False # nums中元素两种状态 选或不选 # 回溯搜索所有情况 时间复杂度是指数级 # 本题是个很明显的01背包问题: 用n个物品装满容积为w的背包最大价值是多少? # ( 怎么就是最大价值了呢? nums[i]即是重量也是价值,所以最大价值等于背包容量 ) n = len( nums ) w = total // 2 # dp[ j ] 表示是否能够装满 j dp = [ False for _ in range( w + 1 ) ] # 初始化非常重要 # 其实这个初始化没什么意义 只是为了辅助递推 # 非要赋予其意义的话 nums中元素可以装满0 ( 什么都不选 ) dp[ 0 ] = True for i in range( n ): for j in range( w, nums[ i ] - 1, -1 ): dp[ j ] = dp[ j ] or dp[ j - nums[ i ] ] return dp[ -1 ] ``` ## 更加直白的写法 ```python class Solution: def canPartition(self, nums: List[int]) -> bool: total = 0 for v in nums: total += v if total % 2 == 1: return False n = len( nums ) w = total // 2 dp = [ 0 for _ in range( w + 1 ) ] for i in range( n ): for j in range( w, nums[ i ] - 1, -1 ): dp[ j ] = max( dp[ j ], dp[ j - nums[ i ] ] + nums[ i ] ) return dp[ -1 ] == w ```