Partion Equal Subset Sum ? 授课代码有点儿小问题

来源：9-7 面试中的0-1背包问题 Partition Equal Subset Sum

triump

2018-11-27

老师，你的代码有点儿问题，下面的memo[0] 应该初始化为true?
class Solution {

public:
bool canPartition(vector& nums) {

    int sum = 0;
    for(int i = 0 ; i < nums.size() ; i ++){
        assert(nums[i] > 0);
        sum += nums[i];
    }

    if(sum % 2)
        return false;

    int n = nums.size();
    int C = sum / 2;
    vector<bool> memo(C + 1, false);
    for(int i = 0 ; i <= C ; i ++)
        memo[i] = (nums[0] == i);

    for(int i = 1 ; i < n ; i ++)
        for(int j = C; j >= nums[i] ; j --)
            memo[j] = memo[j] || memo[j - nums[i]];

    return memo[C];
}

};

写回答

1回答

liuyubobobo

2018-11-27

已采纳

赞！

从memo的语义来讲，应该初始化为true。

不过，在这个问题中，由于有限定条件，nums中的所有元素一定为正，且nums非空。所以C = 0一定不是原问题的解。所以说memo[0]=false也ok：）

实际上，由于这个限制，在这个递推过程中，memo[0]的值根本不会影响结果。因为在递推过程中，访问memo[0]的时候，只有可能是j - nums[i] == 0的情况，而此时，memo[j]一定为true（因为memo初始化的方式）。所以memo[0]是多少不会影响||逻辑的结果：）

不信试一试，显示地将memo[0]初始化为true或者false，程序都是正确的：）

继续加油！

liuyubobobo

MarcoLiLiLi

在上面的代码中，如果没有 for(int i = 0 ; i <= C ; i ++) memo[i] = (nums[0] == i); 这个初始条件的话，memo[0] 不设成 true，程序就是错误的。但是，一旦有了这个初始化，在题目的限制条件下，是正确的。因为，如果这个和只由一个数字填充，在这个初始化的时候，肯定找到了；但如果有多个数字填充，那么 nums[0] 一定发挥了作用，那么在访问到 j - nums[i] == 0 的时候，这个 j 肯定也已经使用其他数字的和组成了。用你的这个测试用例，运行一下上面的代码，试试看？不过，确实，初始使用 memo[0] = true 的方式更好。我有时间补充一下相关的讲解。谢谢建议！：）

2020-03-17

共2条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

查看课程

相似问题

416题求助

回答 1

leetcode112题的一个小问题

回答 1

416. Partition Equal Subset Sum 代码优化

回答 1

leetcode416题 partition equal subset sum 疑问

回答 1

关于Two Sum问题中数据重复的问题

回答 3

打开慕课网App查看更多内容