leetcode416题 partition equal subset sum 疑问

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

weixin_慕慕4340848

2021-02-07

老师您好。这道题我有个疑问。麻烦您看一下下面的注释内容,谢谢!

 bool canPartition(vector<int>& nums) {
        int sum=0;

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

        if(sum%2!=0)
        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);
        **memo[0]=true;**//这里是不是应该把memo[0]设置为true呢,因为对于任意范围的数据,不选择任何数,就可以满足容量为0的情况,这样理解对吗?
        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

2021-02-07

是的。可以参考这里:http://coding.imooc.com/learn/questiondetail/188433.html


继续加油!:)

0
0

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

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

7410 学习 · 1150 问题

查看课程