Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

NOTE:
1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int canPartition(int *nums, int numsSize);

int main()
{
    int nums[] = {1,5,11,5};
    int n = 4;
    int can = 0;

    can = canPartition(nums,n);
    printf("result is: %d\n",can);

    return 0;
}

int canPartition(int *nums, int numsSize)
{
    int i = 0, j = 0;
    int total = 0;
    int half = 0;
    int max = 0;
    int *sum; // sum[i]=1表示和等于i

    for(i = 0; i < numsSize; i++)
    {
        total += nums[i];
        max = max > nums[i] ? max : nums[i];
    }

    if(total%2) return 0; // 和为奇数，不能划分为等和子集
    if(max > total/2) return 0; // 最大元素大于和的一半，不能划分为等和子集

    half = total/2;
    sum = (int *)malloc((half+1)*sizeof(int));
    memset(sum,0,(half+1)*sizeof(int));

    sum[0] = 1; // 和等于0一定成立，空集就行
    for(i = 0; i < numsSize; i++)
    {
        for(j = half; j >= nums[i]; j--)
        {
            if(sum[j-nums[i]])
            {
                sum[j] = 1;
                if(j == half)
                {
                    return 1;
                }
            }
        }
    }

    return 0;
}

标签: none

已有 12 条评论

  1. zyeqeorvws zyeqeorvws

    博主真是太厉害了！！！

    回复
  2. isddjhmwjj isddjhmwjj

    不错不错，我喜欢看 https://www.jiwenlaw.com/

    回复
  3. qsuwwkpdtb qsuwwkpdtb

    想想你的文章写的特别好https://www.ea55.com/

    回复
  4. abpihgsxvz abpihgsxvz

    《戴帽子的猫》喜剧片高清在线免费观看：https://www.jgz518.com/xingkong/34719.html

    回复
  5. prrponzlch prrponzlch

    《加油，印度！》剧情片高清在线免费观看：https://www.jgz518.com/xingkong/135335.html

    回复
  6. okottgxkvj okottgxkvj

    《困兽国语》动作片高清在线免费观看：https://www.jgz518.com/xingkong/27211.html

    回复
  7. dbreujyutt dbreujyutt

    情感真挚，直击人心，引发强烈共鸣。

    回复
  8. qxcraxozki qxcraxozki

    情感表达稍显含蓄，可适当强化渲染。

    回复
  9. hpiuxzacet hpiuxzacet

    作者对主题的挖掘深入骨髓，展现了非凡的洞察力和理解力。

    回复
  10. szympfrmwx szympfrmwx

    这篇文章不错！

    回复
  11. ezgarlvcjg ezgarlvcjg

    做了几十年的项目 我总结了最好的一个盘（纯干货）coinsrore.com

    回复
  12. rvicsmrszr rvicsmrszr

    2025年10月新盘 做第一批吃螃蟹的人coinsrore.com
    新车新盘 嘎嘎稳 嘎嘎靠谱coinsrore.com
    新车首发，新的一年，只带想赚米的人coinsrore.com
    新盘 上车集合 留下 我要发发 立马进裙coinsrore.com
    做了几十年的项目 我总结了最好的一个盘（纯干货）coinsrore.com
    新车上路，只带前10个人coinsrore.com
    新盘首开 新盘首开 征召客户！！！coinsrore.com
    新项目准备上线，寻找志同道合 的合作伙伴coinsrore.com
    新车即将上线 真正的项目，期待你的参与coinsrore.com
    新盘新项目，不再等待，现在就是最佳上车机会！coinsrore.com
    新盘新盘 这个月刚上新盘 新车第一个吃螃蟹！coinsrore.com

    回复
取消回复

添加新评论