写点什么

[Day19]-[动态规划] 分割等和子集

作者:方勇(gopher)
  • 2022 年 4 月 18 日
  • 本文字数:526 字

    阅读完需:约 2 分钟

416. 分割等和子集

难度中等 1267 收藏分享切换为英文接收动态反馈

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

 

示例 1:

输入:nums = [1,5,11,5]输出:true解释:数组可以分割成 [1, 5, 5] 和 [11] 。
复制代码

示例 2:

输入:nums = [1,2,3,5]输出:false解释:数组不能分割成两个元素和相等的子集。
复制代码

题解:

func canPartition(nums []int) bool {	var solution func(nums []int) bool	solution = func(nums []int) bool {		n, sum := len(nums), 0		for _, v := range nums {			sum += v		}		if sum%2 != 0 {			return false		}		sum = sum / 2		var dp = make([][]bool, n+1)		// base case		// dp[i][j] 表示前i个数组合是否和为j		for i := 0; i <= n; i++ {			dp[i] = make([]bool, sum+1)			dp[i][0] = true // 背包为空的时候,相等于装满了		}		for i := 1; i <= n; i++ {			for j := 1; j <= sum; j++ {				if j-nums[i-1] < 0 { // 数过大,保持上个状态不变					dp[i][j] = dp[i-1][j]				} else {					dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]				}			}		}		return dp[n][sum]	}
return solution(nums)}
复制代码


用户头像

Dead or Alive. 生存战斗是知识的源泉! 2018.11.08 加入

我是一名SRE哨兵,目前是好大夫基础架构部高级工程师。专注于 SRE,微服务、中间件的稳定性和可用性建设,整体负责好大夫服务治理云平台的设计和搭建!

评论

发布
暂无评论
[Day19]-[动态规划]分割等和子集_LeetCode_方勇(gopher)_InfoQ写作平台