Leetcode - partition-equal-subset-sum
https://leetcode.com/problems/partition-equal-subset-sum/
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
- Each of the array element will not exceed 100.
- The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | func canPartition(nums []int) bool { if len(nums) == 0 { return false } sum := 0 for _, n := range nums { sum += n } if sum % 2 == 1 { return false } subSum := sum / 2 dp := make([][]bool, subSum+1) for i := 0; i <= subSum; i++{ dp[i] = make([]bool, len(nums)+1) } dp[0][0] = true for i := 1; i <= subSum; i++ { dp[i][0] = false } for j := 1; j <= len(nums); j++ { dp[0][j] = true } for i := 1; i <= subSum; i++ { for j := 1; j <= len(nums); j++ { if i - nums[j-1] >= 0 { dp[i][j] = dp[i][j-1] || dp[i-nums[j-1]][j-1] } } } return dp[subSum][len(nums)]} |
评论 (0)
