416.分割等和子集 416.分割等和子集

思路：动态规划 dp[i][j]前i个数中能否组成和为j的子数组

class Solution: def canPartition(self, nums: List[int]) -> bool: size = len(nums) s = sum(nums) if s & 1 == 1: return False target = s // 2 dp = [[False for _ in range(target + 1)] for _ in range(size)] for i in range(target + 1): dp[0][i] = False if nums[0] != i else True for i in range(1, size): for j in range(target + 1): if j >= nums[i]: dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]] else: dp[i][j] = dp[i - 1][j] return dp[-1][-1]

判断是否可以把一组数字分为两堆，两堆数字的和相等
思路：首先要判断所有数字的和是不是偶数，然后我们使用一个长度为2的数组进行保存我们要平分得到的target，这么做是我们可以通过使用-，+两种操作来跳过一些数字。

class Solution: def canPartition(self, nums): """ :type nums: List[int] :rtype: bool """ _sum = sum(nums) div, mod = divmod(_sum, 2) if mod or max(nums) > div: return False nums.sort(reverse = True) target = [div] * 2 #一开始将 target 数组设为目标值，然后减去 nums 里的每个数 return self.dfs(nums, 0, target)def dfs(self, nums, index, target): for i in range(2): if target[i] >= nums[index]: target[i] -= nums[index] if target[i] == 0 or self.dfs(nums, index + 1, target): return True target[i] += nums[index] return False

【416.分割等和子集】代码中，根据下一层 return 的True/False 来定义当前层递归 return 的True/False，如果下一层 return 的是 False，再加回当前的数字消除前面-num[index]的影响。