力扣hot100 分割等和子集 变形01背包 滚动数组优化

发布时间:2024年01月19日

Problem: 416. 分割等和子集
在这里插入图片描述

思路

👨?🏫 参考地址

在这里插入图片描述
在这里插入图片描述

💖 01背包

复杂度

时间复杂度: O ( n m ) O(nm) O(nm) m m m为数组元素和的一半

空间复杂度: O ( n m ) O(nm) O(nm)

Code

class Solution {
	public boolean canPartition(int[] nums)
	{
		int n = nums.length;
		int sum = 0;
		for (int x : nums)
			sum += x;
		if (sum % 2 == 1)
			return false;
		int m = sum / 2;
//		注意:元素只可选一次
		boolean[][] f = new boolean[n][m + 1];// 表示从前 i 个元素中选,使得这些数恰好 = j 的方案是否可行

		if (nums[0] <= m)
			f[0][nums[0]] = true;

		for (int i = 1; i < n; i++)// 先枚举每个数
		{
			for (int j = 0; j <= m; j++)// 再枚举背包容量
			{
				f[i][j] = f[i - 1][j];// 不选当前数
				if (nums[i] <= j)
//							   不选当前数              选当前数
					f[i][j] = f[i - 1][j] || f[i - 1][j - nums[i]];
			}
			if (f[i][m])// 只要出现一次f[i][m] 为真,即返回 true
				return true;
		}
		return false;
//		return f[n - 1][m];//走到这里必返回false
	}
}

💖 滚动数组优化

复杂度

时间复杂度: O ( n m ) O(nm) O(nm) m m m为数组元素和的一半

空间复杂度: O ( m ) O(m) O(m)

Code

class Solution {
	public boolean canPartition(int[] nums)
	{
		int n = nums.length;
		int sum = 0;
		for (int x : nums)
			sum += x;
		if (sum % 2 == 1)
			return false;
		int m = sum / 2;
//		注意:元素只可选一次
		boolean[] f = new boolean[m + 1];// 表示从前 i 个元素中选,使得这些数恰好 = j 的方案是否可行

		if (nums[0] <= m)
			f[nums[0]] = true;

		for (int i = 1; i < n; i++)// 先枚举每个数
		{
			for (int j = m; j >= nums[i]; j--)// 再枚举背包容量
			{
//							   不选当前数              选当前数
				f[j] = f[j] || f[j - nums[i]];
			}
			if (f[m])// 只要出现一次f[i][m] 为真,即返回 true
				return true;
		}
		return false;
	}
}
文章来源:https://blog.csdn.net/lt6666678/article/details/135686332
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。