Q：給定一個(gè)只包含正整數(shù)的非空數(shù)組。是否可以將這個(gè)數(shù)組分割成兩個(gè)子集，使得兩個(gè)子集的元素和相等。

注意:
每個(gè)數(shù)組中的元素不會(huì)超過 100
數(shù)組的大小不會(huì)超過 200
示例 1:
輸入: [1, 5, 11, 5]
輸出: true
解釋: 數(shù)組可以分割成 [1, 5, 5] 和 [11].
?
示例?2:
輸入: [1, 2, 3, 5]
輸出: false
解釋: 數(shù)組不能分割成兩個(gè)元素和相等的子集

func canPartition(nums []int) bool {n := len(nums)if n < 2 {return false}sum, max := 0, 0for _, v := range nums {sum += vif v > max {max = v}}if sum%2 != 0 {return false}target := sum / 2if max > target {return false}dp := make([]bool, target+1)dp[0] = truefor i := 0; i < n; i++ {v := nums[i]for j := target; j >= v; j-- {dp[j] = dp[j] || dp[j-v]}}return dp[target] }

dp[i][j] 表示從數(shù)組的 [0,i]下標(biāo)范圍內(nèi)選取若干個(gè)正整數(shù)，是否存在一種選取方案使得被選取的正整數(shù)的和等于j

?

參考地址：https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/fen-ge-deng-he-zi-ji-by-

總結(jié)

以上是生活随笔為你收集整理的有趣的0-1背包问题：分割等和子集的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。