Leetcode 416. Partition Equal Subset Sum (python+cpp)

题目

解析

这其实是个0，1背包问题，设所有数字和为sum，我们的目标是选取一部分物品，使得它们 的总和为 sum/2，只是这道题不需要考虑价值。和前面几道题目一样，这个题目的典型解法还是动态规划，但是我先写recursion的方法，然后看动态规划和recursion之间的对应.至于0，1问题，后面单开一篇文章来讲好了

解法1：recursion + memorization

更前面那些动态规划的题目一样，这边我还是从recursion开始，recursion的逻辑也很简单，设一个remain值，代表当前还需要多少值才能达到我们的target值，target值为sum的一半。每一级recursion的结果有两种情况，一种是包含当前值，一种是跳过当前值。
python代码如下：

class Solution:def canPartition(self, nums: List[int]) -> bool:def dfs(idx,remain):if idx>=len(nums) or remain<0:return Falseif remain in memo:return memo[remain]if remain == 0:return Truememo[remain] =  dfs(idx+1,remain-nums[idx]) or dfs(idx+1,remain)return memo[remain]

解法2：动态规划

定义一个二维bool值dp数组，dp[i][j]代表当到nums数组的i位置时，是否能够合成sum=j。状态转移方程为：

dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]

这边有两个点需要注意：

1. 对于所有j为0的位置，初始化为True，因为sum=0的都可以达成
2. 在二维循环的时候，内侧对于j的循环要从nums[i-1]开始，因为需要访问dp[i-1][j-nums[i-1]]

python代码如下：

class Solution:def canPartition(self, nums: List[int]) -> bool:if sum(nums)%2 != 0:return Falsetarget = sum(nums)//2n = len(nums)dp = [[False]*(target+1) for _ in range(n+1)]for i in range(n+1):dp[i][0] = Truefor i in range(0,n+1):for j in range(nums[i-1],target+1):dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]return dp[n][target]

C++版本如下：

class Solution {
    
public:bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(),nums.end(),0);if (sum%2 != 0) return false;int target = sum/2;int m = nums.size();vector<vector<bool>> dp(m+1,vector<bool>(target+1,false));for (int i=0;i<=m;i++){
    dp[i][0] = true;}for (int i=1;i<=m;i++){
    for (int j=nums[i-1];j<=target;j++){
    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];}}return dp[m][target];}
};

但是，今天在做一个OA的时候，发现其实我这种0，1背包的解法是错的，居然能过leetcode的所有testcase，很惊奇
第一个错误在于，i应该从1开始，如果i从0开始，那么nums[i-1]就不对了。
第二个错误是，如果j的循环只从nums[i-1]开始，那么小于nums[i-1]的位置都不会被更新，这显然也是不对的，正确的写法应该如下：

class Solution:def canPartition(self, nums: List[int]) -> bool:_sum = sum(nums)if _sum%2 != 0:return Falsetarget = _sum//2dp = [[False]*(target+1) for _ in range(len(nums)+1)]for i in range(len(nums)+1):dp[i][0] = Truefor i in range(1,len(nums)+1):for j in range(target+1):if nums[i-1]<=j:dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]else:dp[i][j] = dp[i-1][j]return dp[-1][-1]

这个模板要记住