![[Swift]LeetCode698. 划分为k个相等的子集 | Partition to K Equal Sum Subsets,第1张](/aiimages/%5BSwift%5DLeetCode698.+%E5%88%92%E5%88%86%E4%B8%BAk%E4%B8%AA%E7%9B%B8%E7%AD%89%E7%9A%84%E5%AD%90%E9%9B%86+%7C+Partition+to+K+Equal+Sum+Subsets.png "[Swift]LeetCode698. 划分为k个相等的子集 | Partition to K Equal Sum Subsets,第1张")
Given an array of integers nums and a positive integer k,find whether it‘s possible to divIDe this array into k non-empty subsets whose sums are all equal.
Example 1:
input: nums = [4,3,2,5,1],k = 4Output: TrueExplanation: It‘s possible to divIDe it into 4 subsets (5),(1,4),(2,3),3) with equal sums.
Note:
1 <= k <= len(nums) <= 16. 0 < nums[i] < 10000. 给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
示例 1：
输入： nums = [4,k = 4输出： True说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
注意:
1 <= k <= len(nums) <= 16 0 < nums[i] < 10000 16ms
@H_403_56@1 class Solution { 2 func canPartitionKSubsets(_ nums: [Int],_ k: Int) -> Bool { 3 4 // do a quick check to make sure its even possible 5 let sum = nums.reduce(0,+) 6 guard sum % k == 0 else { 7 return false 8 } 9 10 // sum we want to achIEve for each partition11 let partitionSum = sum / k 12 13 var isVisited = [Bool](repeating: false,count: nums.count)14 15 return canPartitionKSubsets(16 nums: nums,17 numsIndex: 0,18 k: k,19 currentSum: 0,20 expectedSum: partitionSum,21 isVisited: &isVisited)22 }23 24 func canPartitionKSubsets(25 nums: [Int],26 numsIndex: Int,27 k: Int,28 currentSum: Int,29 expectedSum: Int,30 isVisited: inout [Bool]31 ) -> Bool {32 guard currentSum <= expectedSum else {33 // exceed the expected sum so we can‘t form a partition34 return false35 }36 37 if k == 0 {38 return true39 }40 41 if currentSum == expectedSum {42 return canPartitionKSubsets(43 nums: nums,44 numsIndex: 0,// start a brand new search from 045 k: k-1,// we found a partition!46 currentSum: 0,// reset sum47 expectedSum: expectedSum,48 isVisited: &isVisited)49 } else {50 51 for i in numsIndex..<nums.count {52 guard !isVisited[i] else {53 // already used this number for a partition54 continue55 }56 57 isVisited[i] = true // we will take this number for the partition58 let canPartition = canPartitionKSubsets(59 nums: nums,60 numsIndex: i+1,61 k: k,62 currentSum: currentSum + nums[i],63 expectedSum: expectedSum,64 isVisited: &isVisited)65 66 if canPartition {67 return true68 }69 70 isVisited[i] = false71 }72 }73 74 return false75 }76 }
32ms
@H_403_56@1 class Solution { 2 func canPartitionKSubsets(_ nums: [Int],_ k: Int) -> Bool { 3 guard !nums.isEmpty else { 4 return false 5 } 6 7 let totalSum = nums.reduce(0,+) 8 9 guard totalSum % k == 0 else {10 return false11 }12 13 let sum = totalSum / k14 15 var visited = [Bool](repeating: false,count: nums.count)16 17 return canPartitionKSubsets(numbers: nums,k: k,startIndex:0,currentSum: 0,sum: sum,visited: &visited)18 }19 20 func canPartitionKSubsets(numbers: [Int],k: Int,startIndex: Int,currentSum: Int,sum: Int,visited: inout [Bool]) -> Bool {21 guard currentSum <= sum else {22 return false23 }24 25 if currentSum == sum {26 27 if k == 1 {28 return true29 } else {30 // we formed a partition,go try to form another one 31 return canPartitionKSubsets(numbers: numbers,k: k-1,startIndex: 0,visited: &visited) 32 }33 } 34 // currentSum < sum35 else {36 37 for i in startIndex..<numbers.count {38 let number = numbers[i]39 40 if visited[i] {41 continue42 }43 44 visited[i] = true45 46 if canPartitionKSubsets(numbers: numbers,startIndex: i+1,currentSum: currentSum + number,visited: &visited) {47 return true48 }49 50 visited[i] = false51 }52 }53 54 return false55 }56 }
60ms
@H_403_56@1 class Solution { 2 func canPartitionKSubsets(_ nums: [Int],_ k: Int) -> Bool { 3 let sum = nums.reduce(0,+) 4 guard sum % k == 0 else { return false } 5 let bucketTarget = sum / k 6 let maxSubsets = (1<<nums.count) 7 var cache = [Bool?](repeating: nil,count: maxSubsets) 8 return canPartitionSubsets(nums,0,bucketTarget,&cache) 9 }10 11 private func canPartitionSubsets(12 _ nums: [Int],13 _ bitset: Int,14 _ remainingInBucket: Int,15 _ bucketTarget: Int,16 _ cache: inout [Bool?]) -> Bool {17 if let cached = cache[bitset] {18 return cached19 }20 let allElementBitSet = (1<<nums.count) - 121 if bitset == allElementBitSet && remainingInBucket == bucketTarget {22 // All elements are set and all buckets are filled.23 return true24 }25 for i in 0..<nums.count {26 guard bitset & (1<<i) == 0 else { continue }27 guard nums[i] <= remainingInBucket else { continue }28 var updatedRemainingInBucket = remainingInBucket - nums[i]29 if updatedRemainingInBucket == 0 {30 updatedRemainingInBucket = bucketTarget // Create a new bucket31 }32 if canPartitionSubsets(33 nums,34 bitset | (1<<i),35 updatedRemainingInBucket,36 bucketTarget,37 &cache) {38 cache[bitset] = true39 return true40 }41 }42 cache[bitset] = false43 return false44 }45 }
88ms
@H_403_56@1 class Solution { 2 func canPartitionKSubsets(_ nums: [Int],_ k: Int) -> Bool { 3 if nums.count == 0 && k == 0 { 4 return true 5 } 6 guard nums.count > 0,k > 0 else { 7 return false 8 } 9 var target = nums.reduce(0,+)10 if target % k != 0 {11 return false12 } 13 target = target/k14 15 16 func canPart(index:Int,remain:Int,curSum: Int,visited:[Int: Bool]) -> Bool {17 if remain == 0 {18 return true19 }20 21 if index == nums.count {22 return false23 }24 25 if curSum == target {26 return canPart(index:0,remain:remain - 1,curSum:0,visited:visited)27 } else if curSum > target {28 return false29 }30 31 for i in index..<nums.count {32 var visited = visited33 if visited[i] == true {34 continue35 } else {36 visited[i] = true37 if canPart(index:i,remain:remain,curSum: curSum + nums[i],visited: visited) {38 return true39 }40 visited[i] = false41 }42 }43 44 return false45 }46 47 return canPart(index:0,remain:k,curSum: 0,visited:[Int: Bool]())48 }49 }
92ms
@H_403_56@1 class Solution { 2 //We Could use dfs. start from the first index,find the combination where num1 + num2 .. + num3 == target. Then start from index 0 with memory of which numbers has been used. 3 func canPartitionKSubsets(_ nums: [Int],_ k: Int) -> Bool { 4 if nums.count == 0 && k == 0 { 5 return true 6 } 7 guard nums.count > 0,k > 0 else { 8 return false 9 }10 var target = nums.reduce(0,+)11 //Remember to check if the target can be fully divIDed by k12 if target % k != 0 {13 return false14 }15 target = target/k16 17 func canPart(index:Int,visited:[Int: Bool]) -> Bool {18 if remain == 0 {19 return true20 } 21 22 if index == nums.count {23 return false24 } 25 26 if curSum == target {27 return canPart(index: 0,remain: remain - 1,visited: visited)28 } else if curSum > target {29 return false30 }31 32 for i in index..<nums.count {33 var visited = visited34 if visited[i] == true {35 continue36 }37 visited[i] = true38 if canPart(index: i,remain: remain,visited: visited) {39 return true40 }41 } 42 return false43 } 44 return canPart(index:0,visited:[Int: Bool]())45 }46 }
96ms
@H_403_56@1 class Solution { 2 func canPartitionKSubsets(_ nums: [Int],_ k: Int) -> Bool { 3 var sum = 0 4 for num in nums { 5 sum += num 6 } 7 if k <= 0 || sum % k != 0 { 8 return false 9 }10 var visited = Array(repeating: false,count: nums.count)11 return canPartition(nums,&visited,k,sum / k)12 }13 14 private func canPartition(_ nums: [Int],_ visited: inout [Bool],_ start_index: Int,_ k: Int,_ cur_sum: Int,_ cur_num: Int,_ target: Int) -> Bool {15 if k == 1 {16 return true17 }18 if cur_sum == target && cur_num > 0 {19 return canPartition(nums,k - 1,0,target)20 }21 for i in start_index..<nums.count {22 if !visited[i] {23 visited[i] = true24 let match = canPartition(nums,i + 1,cur_sum + nums[i],cur_num + 1,target)25 if match {26 return true27 }28 visited[i] = false29 }30 }31 return false32 }33 }Runtime: 244 ms Memory Usage: 19.1 MB @H_403_56@
1 class Solution { 2 func canPartitionKSubsets(_ nums: [Int],_ k: Int) -> Bool { 3 var nums = nums 4 nums.sort() 5 var sum:Int = nums.reduce(0,+) 6 if sum % k != 0 {return false} 7 var v:[Int] = [Int](repeating:0,count:k) 8 return helper(&nums,sum / k,&v,nums.count - 1) 9 }10 11 func helper(_ nums:inout [Int],_ target:Int,_ v:inout [Int],_ IDx:Int) -> Bool12 {13 if IDx == -114 {15 for t in v16 {17 if t != target {return false} 18 }19 return true20 }21 var num:Int = nums[IDx]22 for i in 0..<v.count23 {24 if v[i] + num > target {continue}25 v[i] += num26 if helper(&nums,target,IDx - 1)27 {28 return true29 }30 v[i] -= num31 }32 return false 33 }34 }总结
以上是内存溢出为你收集整理的[Swift]LeetCode698. 划分为k个相等的子集 | Partition to K Equal Sum Subsets全部内容，希望文章能够帮你解决[Swift]LeetCode698. 划分为k个相等的子集 | Partition to K Equal Sum Subsets所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）