【算法与数据结构】416、LeetCode分割等和子集

这篇具有很好参考价值的文章主要介绍了【算法与数据结构】416、LeetCode分割等和子集。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

【算法与数据结构】416、LeetCode分割等和子集,算法,算法

二、解法

  思路分析:本题可以抽象成一个01背包的问题,关于01背包可以看【算法与数据结构】算法与数据结构知识点。本题只需要求出数组的累积和,然后和的一半就可以视为背包的最大重量,目标就是要判断数组中是否有和为背包最大重量的子集。其中,物品重量和价值相同,就是数组元素的值。根据01背包的思想,我们写出如下一维滚动数组的代码。
  程序如下

class Solution {
public:
	bool canPartition(vector<int>& nums) {
		int sum = 0;
		for (int i : nums) sum += i;	// 也可以用accumalte函数
		if (sum % 2 != 0 || nums.size() < 2) return false;
		vector<int> dp(sum/2 + 1, 0);
		for (int i = 0; i < nums.size(); i++) {
			for (int j = sum / 2; j >= nums[i]; j--) {
				dp[j] = max(dp[j], dp[j - nums[i] ] + nums[i]);
			}
		}
		if (dp[sum / 2] == sum / 2) return true;
		return false;
	}
};

复杂度分析:

  • 时间复杂度: O ( n 2 ) O(n^2) O(n2)
  • 空间复杂度: O ( n ) O(n) O(n)

三、完整代码

# include <iostream>
# include <vector>
# include <numeric>
# include <algorithm>
using namespace std;

class Solution {
public:
	bool canPartition(vector<int>& nums) {
		int sum = 0;
		for (int i : nums) sum += i;	// 也可以用accumalte函数
		if (sum % 2 != 0 || nums.size() < 2) return false;
		vector<int> dp(sum/2 + 1, 0);
		for (int i = 0; i < nums.size(); i++) {
			for (int j = sum / 2; j >= nums[i]; j--) {
				dp[j] = max(dp[j], dp[j - nums[i] ] + nums[i]);
			}
		}
		if (dp[sum / 2] == sum / 2) return true;
		return false;
	}
};

int main() {
	vector<int> nums = { 1,5,11,5 };
	Solution s1;
	bool result = s1.canPartition(nums);
	cout << result << endl;
	system("pause");
	return 0;
}

end文章来源地址https://www.toymoban.com/news/detail-803066.html

到了这里,关于【算法与数据结构】416、LeetCode分割等和子集的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 01背包问题-递推公式的自我理解与LeetCode 416. 分割等和子集

    学算法好痛苦,完全是对我智力的一次次折磨,看了好多博客,对二维dp数组的理解都是直接搬了代码随想录,搬了随想录又没详细解释,大家都是一眼看懂的吗,好吧() 如果有一个容量为 j 的这样的背包——一个独立的,容量为j的背包。(没把它理解为“剩余容量”) 对于

    2024年02月07日
    浏览(43)
  • [Leetcode] 416. 分割等和子集、1049. 最后一块石头的重量 II、494. 目标和、474. 一和零

    内容:今天复习下dp数组中的背包问题 分割等和子集 - 能否装满 最后一块石头 - 尽可能装满 目标和 - 有多少种方法装 一和零 - 装满背包有多少个物品 416. 分割等和子集 10背包:用/不用;有容量;有价值 dp[j] : 容量为j,最大价值为dp[j]         重量和价值等价 dp[target] == t

    2024年02月16日
    浏览(41)
  • 代码随想录 Day35 动态规划04 01背包问题和完全背包问题 LeetCode T416 分割等和子集

    说到背包问题大家都会想到使用动规的方式来求解,那么为什么用动规呢, dp数组代表什么呢 ? 初始化是什么 , 遍历方式又是什么 ,这篇文章笔者将详细讲解背包问题的经典例题0-1背包问题和完全背包问题的解题方式,希望能帮助到大家 有人一提到背包问题就只会使用动态规划来

    2024年02月06日
    浏览(71)
  • 算法训练第四十二天|01背包问题 二维 、01背包问题 一维、416. 分割等和子集

    视频链接:https://www.bilibili.com/video/BV1cg411g7Y6/ 参考:https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html 对于面试的话,其实掌握01背包,和完全背包,就够用了,最多可以再来一个多重背包。 而完全背包又是也是01背包稍作变化而来,即:完全

    2024年02月01日
    浏览(44)
  • 【力扣】416. 分割等和子集 <动态规划、回溯>

    给你一个 只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2: 输入:nums = [1,2,3,5] 输出:false 解释:数组不能分割成两个元素和

    2024年02月10日
    浏览(38)
  • 代码随想录day42|背包问题、416. 分割等和子集

     背包问题:    01 背包 二维数组dp[i][j]解法 纯01背包:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。 每件物品只能用一次 ,求解将哪些物品装入背包里物品价值总和最大。 dp[i][j]:从下标为[0-i]的物品里任意取,放进容量为j的

    2024年04月09日
    浏览(57)
  • 力扣hot100:416.分割等和子集(组合/动态规划/STL问题)

    组合数问题 我们思考一下,如果要把数组分割成两个子集,并且两个子集的元素和相等,是否等价于在数组中寻找若干个数使之和等于所有数的一半?是的! 因此我们可以想到,两种方式: ①回溯的方式找到target,但是回溯是阶乘级别的算法,这里会超时。 ②从前往后遍历

    2024年04月28日
    浏览(36)
  • 【Day42】代码随想录之动态规划0-1背包_416. 分割等和子集

    动态规划理论基础 动规五部曲: 确定dp数组 下标及dp[i] 的含义。 递推公式:比如斐波那契数列 dp[i] = dp[i-1] + dp[i-2]。 初始化dp数组。 确定遍历顺序:从前到后or其他。 推导dp数组。 出现结果不正确: 打印dp日志和自己想的一样:递推公式、初始化或者遍历顺序出错。 打印

    2024年02月20日
    浏览(63)
  • 【十七】【动态规划】DP41 【模板】01背包、416. 分割等和子集、494. 目标和,三道题目深度解析

    动态规划就像是解决问题的一种策略,它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题,并将每个小问题的解保存起来。这样,当我们需要解决原始问题的时候,我们就可以直接利用已经计算好的小问题的解,而不需要重

    2024年02月03日
    浏览(43)
  • Day42|动态规划part04: 01背包问题,你该了解这些!、滚动数组、416. 分割等和子集

    其他背包,面试几乎不会问,都是竞赛级别的了,leetcode上连多重背包的题目都没有,所以题库也告诉我们,01背包和完全背包就够用了。 而完全背包又是也是01背包稍作变化而来,即:完全背包的物品数量是无限的。 01 背包问题描述 有n件物品和一个最多能背重量为w 的背包

    2024年04月25日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包