LC.416 Partition Equal Subset Sum

标准背包解法

经典01背包问题

class Solution(object): def canPartition1(self, nums): """ dp[i][j] 表示是否能用前i个元素组成和为j 那么dp[i][j] = dp[i-1][j] (表示不用第i个元素)or dp[i-1][j-nums[i]] 表示用第i个元素 """ sumer = sum(nums) if sumer & 1 == 1: return False dp = [[False] * (sumer//2 + 1) for _ in range(len(nums)+1)] dp[0][0] = True for i in range(1, len(dp)): for j in range(1, len(dp[0])): dp[i][j] = dp[i-1][j] if j - nums[i-1] >= 0: dp[i][j] |= dp[i-1][j-nums[i-1]] return dp[-1][-1]

空间优化

上面应该是最标准的解法，但是会超时 在空间上的优化；

def canPartition2(self, nums): """ 可以在空间上进行优化 第 i 行的第 j 个元素只用到了第 i-1行的元素，没有用到第 i 行的 前 j - 1个元素 所以可以从后往前更新，这样不会重复使用元素， 如果从左往右遍历那就变成了完全背包问题 """ sumer = sum(nums) if sumer & 1 == 1: return False dp = [False] * (sumer // 2 + 1) dp[0] = True for i in range(len(nums)): for j in range(len(dp)-1, -1, -1): if j - nums[i] >= 0: dp[j] |= dp[j - nums[i]] else: break return dp[-1]

DFS写法

def canPartition3(self, nums): """ 超时 """ sumer = sum(nums) if sumer & 1 == 1: return False from functools import lru_cache @lru_cache() def DFS(index, target): if target == 0: return True if index == len(nums): return False return DFS(index + 1, target ) or DFS(index + 1, target - nums[index]) return DFS(0, sumer // 2)

排序优化

对于求均和问题，一般会先排序，排序的原因如下： 假如现在数组为[1,1,1,1,4]， 如果从小到大排列，那么前四个数才能组成target,如果从大到小排列，那么第一个数就等于target. 所以求targert的时候尽可能的把大数先用掉，这样可以节省一定的时间。

class Solution: def canPartition(self, nums): sumer = sum(nums) if sumer & 1 == 1: return False nums.sort(reverse=True) print(nums) def DFS(index, target): if target == 0: return True if index == len(nums) or target < 0: return False return DFS(index + 1, target - nums[index]) or DFS(index + 1, target) return DFS(0, sumer // 2)

利用set来解

讲第i个数和前i-1个数的和相加

def canPartition(self, nums): sumer = sum(nums) if sumer & 1 == 1: return False sumer >>= 1 aset = {0} for num in nums: aset |= set([x + num for x in aset]) return sumer in aset