• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode416. 分割等和子集 | Partition Equal Subset Sum

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:为敢(WeiGanTechnologies)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/10331729.html
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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:

  1. Each of the array element will not exceed 100.
  2. 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.

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

注意:

  1. 每个数组中的元素不会超过 100
  2. 数组的大小不会超过 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode225.用队列实现栈|ImplementStackusingQueues发布时间:2022-07-13
下一篇:
swift UI专项训练16 ProgressView进度条发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap