lintcode588. 划分和相等的子集

清疚 2023-05-22 08:56 76阅读 0赞

给一 只含有正整数 的 非空 数组, 找到这个数组是否可以划分为 两个 元素和相等的子集。

样例
    例1:
    
    输入: nums = [1, 5, 11, 5], 
    输出: true
    解释:
    two subsets: [1, 5, 5], [11]
    例2:
    
    输入: nums = [1, 2, 3, 9], 
    输出: false
    注意事项
    所有数组元素不超过100.
    数组大小不超过200.

思路：先求出数组的总和，如果和是奇数的话，则不可能划分为相等的子集。  
如果和是偶数的话，则取其一半，进行01背包，看看和的一半能不能查找到即可

class Solution {
        
    public:
        /**
         * @param nums: a non-empty array only positive integers
         * @return: true if can partition or false
         */
        bool canPartition(vector<int> &nums) {
        
            // write your code here
            int sum=0;
            for (int i = 0; i < nums.size(); i++) {
        
                sum+=nums[i];
            }
            if(sum%2) return false;
            int half=sum/2;
            vector<bool> dp(half+1,false);
            dp[0]=true;
            for (int i = 0; i < nums.size(); i++) {
        
                for(int j = half;j>=nums[i];j--)
                {
        
                    if(dp[j-nums[i]]) dp[j]=true;
                }
            }
            return dp[half];
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，76人围观）

还没有评论，来说两句吧...

相关阅读

相关【力扣 leetcode】698：划分为k个相等的子集

每日进步剪枝：通过判断避免一些不必要的遍历过程。可行性剪枝：方案不可行时，回溯。最优性剪枝: 方案的解不可能优于当前

迷南。/ 2023年10月09日 14:46/ 0 赞/ 99 阅读

相关 LeetCode - 698 划分为k个相等的子集

目录题目来源题目描述示例提示题目解析算法源码 -------------------- 题目来源 [698. 划分为k个相等的子集 - 力扣（

待我称王封你为后i/ 2023年09月23日 14:32/ 0 赞/ 147 阅读

相关 Java实现 LeetCode 698 划分为k个相等的子集(递归)

698. 划分为k个相等的子集给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。示例 1：输入： num

谁践踏了优雅/ 2023年07月23日 05:00/ 0 赞/ 97 阅读

相关 lintcode 761. 最小子集

给一非负整数数组. 取数组中的一部分元素, 使得它们的和大于数组中其余元素的和, 求出满足条件的元素数量最小值. 样例例1: 输入:

灰太狼/ 2023年05月22日 12:28/ 0 赞/ 38 阅读

相关 lintcode588. 划分和相等的子集

给一只含有正整数的非空数组, 找到这个数组是否可以划分为两个元素和相等的子集。样例例1: 输入: nums = [1, 5,

清疚/ 2023年05月22日 08:56/ 0 赞/ 77 阅读

相关 lintcode724. 最小划分

给出一个正整数数组，写一个程序把这个整数数组分成S1跟S2两部分，使S1中的和跟S2中的和的差的绝对值最小。换句话讲，如果有一个一个整数数组 S 有 n 个数，如果Subset

阳光穿透心脏的1/2处/ 2023年05月21日 15:29/ 0 赞/ 96 阅读

相关 698 划分为k个相等的子集（dfs减枝）

1. 问题描述：给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。示例 1：输入： nums = \[4,

落日映苍穹つ/ 2022年09月03日 11:22/ 0 赞/ 172 阅读

相关 LintCode每日一练-限制条件子集

问题：限制条件子集 -------------------- 给一个数组，给定一个target，求满足以下条件的子集个数：条件：子集中的最小值+最大值小于给定ta

小鱼儿/ 2022年05月30日 09:07/ 0 赞/ 311 阅读

相关【lintcode】子集问题

这里的子集问题是指给定一个列表求它的所有不重复子集的问题。这个问题分为两类：一类是所给列表包含重复元素，另一类是所给列表不含重复元素。分别对应lintcode中17和18题。

梦里梦外;/ 2022年05月24日 08:45/ 0 赞/ 296 阅读

相关子集和问题：按给定子集和完全划分集合

需求是这样的：有44个数字A1-A44：1420, 1198, 493, 300, 3006, 881, 2450, 1372, 3643, 1350, 598, 615

柔情只为你懂/ 2022年02月04日 16:09/ 0 赞/ 350 阅读