★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：为敢（WeiGanTechnologies）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10331729.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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].
Example 2:
Input: [1, 2, 3, 5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集.
32ms
1 class Solution { 2 var mark = [String : Bool]() 3 func canPartition(_ nums: [Int]) -> Bool { 4 let count = nums.count 5 var sum = 0 6 for i in 0..<count { 7 sum += nums[i] 8 } 9 10 if sum & 1 == 1 { 11 return false 12 } 13 return reachTarget(nums, count, 0, sum / 2) 14 } 15 16 func reachTarget(_ nums: [Int], _ count: Int, _ index: Int, _ target: Int) -> Bool { 17 let key = "\(index),\(target)" 18 if let _ = mark[key] { 19 return false 20 } 21 if target == 0 { 22 return true 23 } else if target < 0 { 24 return false 25 } 26 if index == count { 27 return false 28 } 29 30 if reachTarget(nums, count, index + 1, target - nums[index]) { 31 return true 32 } 33 if reachTarget(nums, count, index + 1, target) { 34 return true 35 } 36 37 mark[key] = false 38 return false 39 } 40 }
40ms
1 class Solution { 2 func canPartition(_ nums: [Int]) -> Bool { 3 var sum = 0 4 for num in nums { 5 sum += num 6 } 7 8 if sum % 2 == 1 { 9 return false 10 } 11 let numsCount = nums.count 12 let target = sum / 2 13 let invalidArray = Array(repeating: false, count: target + 1) 14 var invalidMatrix = Array(repeating: invalidArray, count: numsCount + 1) 15 return helper(nums: nums, currentIndex: 0, target: target, invalidMatrix: &invalidMatrix) 16 } 17 18 func helper(nums: [Int], currentIndex: Int, target: Int, invalidMatrix: inout [[Bool]]) -> Bool { 19 if invalidMatrix[currentIndex][target] { 20 return false 21 } 22 23 let arrayCount = nums.count 24 for i in currentIndex ..< arrayCount { 25 let newTarget = target - nums[i] 26 if newTarget == 0 { 27 return true 28 } 29 if newTarget < 0 { 30 break 31 } 32 33 if (i + 1) < arrayCount 34 && helper(nums: nums, currentIndex: i + 1, target: newTarget, invalidMatrix: &invalidMatrix) { 35 return true 36 } 37 } 38 invalidMatrix[currentIndex][target] = true 39 return false 40 } 41 }
3456ms
1 class Solution { 2 func canPartition(_ nums: [Int]) -> Bool { 3 var sum:Int = nums.reduce(0, +) 4 var target:Int = sum >> 1 5 if (sum & 1) == 1 {return false} 6 var dp:[Bool] = [Bool](repeating:false,count:target + 1) 7 dp[0] = true 8 for num in nums 9 { 10 if num > target {continue} 11 for i in (num...target).reversed() 12 { 13 dp[i] = dp[i] || dp[i - num] 14 } 15 } 16 return dp[target] 17 } 18 }
3504ms
1 class Solution { 2 func canPartition(_ nums: [Int]) -> Bool { 3 var nums = nums 4 if nums.count == 0 { 5 return true 6 } 7 var sum = 0 8 nums = nums.sorted() 9 for num in nums { 10 sum += num 11 } 12 if sum % 2 != 0 { 13 return false 14 } 15 sum = sum / 2 16 if nums.last! > sum { 17 return false 18 } 19 var dp = [Bool](repeating: false, count: sum + 1) 20 dp[0] = true 21 for i in 1...nums.count { 22 for j in (nums[i - 1]...sum).reversed() { 23 dp[j] = dp[j] || dp[j - nums[i - 1]] 24 } 25 } 26 return dp[sum] 27 } 28 }
请发表评论