416. 分割等和子集
题目简述：
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
思路：
1. 转换为能否从数组中找出一些数字，使得这些数字的和恰好等于数组总和的一半，变成0-1背包问题
2. 根据数组的长度n判断数组是否可以被划分。如果n<2，则不可能分割成功
3. 计算整个数组的元素和sum以及最大元素maxNum。
4. 如果sum是奇数，则不可能将数组分割成元素和相等的两个子集，直接返回false
5. 如果sum是偶数，令target=sum/2，如果maxNum>target，同样不可能分割成功，返回false
6. 创建二维数组dp，包含n行target+1列，其中dp[i][j]表示从数组的[0,i]下标范围内选取若干个正整数，是否存在一种选取方案使得被选取的正整数的和等于j。
7. 初始时，dp中的全部元素都为false
8. 如果不选取任何正整数，则被选取的正整数等于0，因此对于所有的0<=i<n，都有dp[i][0]=true
9. 当i==0时，只有一个正整数nums[0]可以被选取，因此dp[0][nums[0]]=true
10. i,j>0时
11. 如果j>=nums[i]，则对于当前的数字nums[i]，可以选取也可以不选取，两种情况只要有一个为true，就有dp[i][j]=true
12. 如果j<nums[i]，则在选取的数字的和等于j的情况下无法选取当前的数字nums[i]，因此有dp[i][j]=dp[i-1][j]
代码如下：
class Solution: def canPartition(self, nums: List[int]) -> bool: n = len(nums) if n < 2: return False total = sum(nums) maxNum = max(nums) if total & 1: return False target = total // 2 if maxNum > target: return False dp = [[False] * (target + 1) for _ in range(n)] for i in range(n): dp[i][0] = True dp[0][nums[0]] = True for i in range(1, n): num = nums[i] for j in range(1, target + 1): if j >= num: dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num] else: dp[i][j] = dp[i - 1][j] return dp[n - 1][target]