[Swift]LeetCode416. 分割等和子集 | 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

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: trueExplanation: The array can be partitioned as [1,5] and [11]. 

Example 2:

input: [1,2,3,5]Output: falseExplanation: The array cannot be partitioned into equal sum subsets.

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

注意:

每个数组中的元素不会超过 100 数组的大小不会超过 200

示例 1:

输入: [1,5]输出: true解释: 数组可以分割成 [1,5] 和 [11]. 

示例 2:

输入: [1,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 false12         }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 false20         }21         if target == 0 {22             return true23         } else if target < 0 {24             return false25         }26         if index == count {27             return false28         }29         30         if reachTarget(nums,index + 1,target - nums[index]) {31             return true32         }33         if reachTarget(nums,index + 1,target) {34             return true35         }36         37         mark[key] = false38         return false39     }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 false10     }11     let numsCount = nums.count12     let target = sum / 213     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 false21     }22 23     let arrayCount = nums.count24     for i in currentIndex ..< arrayCount {25       let newTarget = target - nums[i]26       if newTarget == 0 {27         return true28       }29       if newTarget < 0 {30         break31       }32 33       if (i + 1) < arrayCount34         && helper(nums: nums,currentIndex: i + 1,target: newTarget,invalIDMatrix: &invalIDMatrix) {35         return true36       }37     }38     invalIDMatrix[currentIndex][target] = true39     return false40   }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 += num11         }12         if sum % 2 != 0 {13             return false14         }15         sum = sum / 216         if nums.last! > sum {17             return false18         }19         var dp = [Bool](repeating: false,count: sum + 1)20         dp[0] = true21         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 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode416. 分割等和子集 | Partition Equal Subset Sum全部内容，希望文章能够帮你解决[Swift]LeetCode416. 分割等和子集 | Partition Equal Subset Sum所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。