大佬教程收集整理的这篇文章主要介绍了[Swift]LeetCode698. 划分为k个相等的子集 | Partition to K Equal Sum Subsets，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
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 = 4 Output: True Explanation: 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) <= 160 < nums[i] < 1000016ms
1 @H_673_72@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 @H_673_72@else { 7 @H_673_72@return @H_673_72@false 8 } 9 10 // sum we want to achieve for each partition 11 let partitionSum = sum / k 12 13 @H_673_72@var isVisited = [Bool](repeaTing: @H_673_72@false,count: nums.count) 14 15 @H_673_72@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 @H_673_72@else { 33 // exceed the expected sum so we can‘t form a partition 34 @H_673_72@return @H_673_72@false 35 } 36 37 @H_673_72@if k == 0 { 38 @H_673_72@return @H_673_72@true 39 } 40 41 @H_673_72@if currentSum == expectedSum { 42 @H_673_72@return canPartitionKSubsets( 43 nums: nums,44 numsIndex: 0,// start a brand new search from 0 45 k: k-1,// we found a partition! 46 currentSum: 0,// reset sum 47 expectedSum: expectedSum,48 isVisited: &isVisited) 49 } @H_673_72@else { 50 51 @H_673_72@for i @H_673_72@in numsIndex..<nums.count { 52 guard !isVisited[i] @H_673_72@else { 53 // already used this number for a partition 54 @H_673_72@conTinue 55 } 56 57 isVisited[i] = @H_673_72@true // we will take this number for the partition 58 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 @H_673_72@if canPartition { 67 @H_673_72@return @H_673_72@true 68 } 69 70 isVisited[i] = @H_673_72@false 71 } 72 } 73 74 @H_673_72@return @H_673_72@false 75 } 76 }
32ms
1 @H_673_72@class Solution { 2 func canPartitionKSubsets(_ nums: [Int],_ k: int) -> Bool { 3 guard !nums.isEmpty @H_673_72@else { 4 @H_673_72@return @H_673_72@false 5 } 6 7 let @R_518_10586@lSum = nums.reduce(0,+) 8 9 guard @R_518_10586@lSum % k == 0 @H_673_72@else { 10 @H_673_72@return @H_673_72@false 11 } 12 13 let sum = @R_518_10586@lSum / k 14 15 @H_673_72@var visited = [Bool](repeaTing: @H_673_72@false,count: nums.count) 16 17 @H_673_72@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 @H_673_72@else { 22 @H_673_72@return @H_673_72@false 23 } 24 25 @H_673_72@if currentSum == sum { 26 27 @H_673_72@if k == 1 { 28 @H_673_72@return @H_673_72@true 29 } @H_673_72@else { 30 // we formed a partition,go try to form another one 31 @H_673_72@return canPartitionKSubsets(numbers: numbers,k: k-1,starTindex: 0,visited: &visited) 32 } 33 } 34 // currentSum < sum 35 @H_673_72@else { 36 37 @H_673_72@for i @H_673_72@in starTindex..<numbers.count { 38 let number = numbers[i] 39 40 @H_673_72@if visited[i] { 41 @H_673_72@conTinue 42 } 43 44 visited[i] = @H_673_72@true 45 46 @H_673_72@if canPartitionKSubsets(numbers: numbers,starTindex: i+1,currentSum: currentSum + number,visited: &visited) { 47 @H_673_72@return @H_673_72@true 48 } 49 50 visited[i] = @H_673_72@false 51 } 52 } 53 54 @H_673_72@return @H_673_72@false 55 } 56 }
60ms
1 @H_673_72@class Solution { 2 func canPartitionKSubsets(_ nums: [Int],_ k: int) -> Bool { 3 let sum = nums.reduce(0,+) 4 guard sum % k == 0 @H_673_72@else { @H_673_72@return @H_673_72@false } 5 let bucketTarget = sum / k 6 let maxSubsets = (1<<nums.count) 7 @H_673_72@var cache = [Bool?](repeaTing: nil,count: maxSubsets) 8 @H_673_72@return canPartitionSubsets(nums,0,bucketTarget,&cachE) 9 } 10 11 @H_673_72@private func canPartitionSubsets( 12 _ nums: [Int],13 _ bitset: Int,14 _ remainingInBucket: Int,15 _ bucketTarget: Int,16 _ cache: inout [Bool?]) -> Bool { 17 @H_673_72@if let cached = cache[bitset] { 18 @H_673_72@return cached 19 } 20 let allElementBitSet = (1<<nums.count) - 1 21 @H_673_72@if bitset == allElementBitSet && remainingInBucket == bucketTarget { 22 // All elements are set and all buckets are filled. 23 @H_673_72@return @H_673_72@true 24 } 25 @H_673_72@for i @H_673_72@in 0..<nums.count { 26 guard bitset & (1<<i) == 0 @H_673_72@else { @H_673_72@conTinue } 27 guard nums[i] <= remainingInBucket @H_673_72@else { @H_673_72@conTinue } 28 @H_673_72@var updatedRemainingInBucket = remainingInBucket - nums[i] 29 @H_673_72@if updatedRemainingInBucket == 0 { 30 updatedRemainingInBucket = bucketTarget // Create a new bucket 31 } 32 @H_673_72@if canPartitionSubsets( 33 nums,34 bitset | (1<<i),35 updatedRemainingInBucket,36 bucketTarget,37 &cachE) { 38 cache[bitset] = @H_673_72@true 39 @H_673_72@return @H_673_72@true 40 } 41 } 42 cache[bitset] = @H_673_72@false 43 @H_673_72@return @H_673_72@false 44 } 45 }
88ms
1 @H_673_72@class Solution { 2 func canPartitionKSubsets(_ nums: [Int],_ k: int) -> Bool { 3 @H_673_72@if nums.count == 0 && k == 0 { 4 @H_673_72@return @H_673_72@true 5 } 6 guard nums.count > 0,k > 0 @H_673_72@else { 7 @H_673_72@return @H_673_72@false 8 } 9 @H_673_72@var target = nums.reduce(0,+) 10 @H_673_72@if target % k != 0 { 11 @H_673_72@return @H_673_72@false 12 } 13 target = target/k 14 15 16 func canPart(index:Int,remain:Int,cursum: Int,visited:[Int: Bool]) -> Bool { 17 @H_673_72@if remain == 0 { 18 @H_673_72@return @H_673_72@true 19 } 20 21 @H_673_72@if index == nums.count { 22 @H_673_72@return @H_673_72@false 23 } 24 25 @H_673_72@if cursum == target { 26 @H_673_72@return canPart(index:0,remain:remain - 1,cursum:0,visited:visited) 27 } @H_673_72@else @H_673_72@if cursum > target { 28 @H_673_72@return @H_673_72@false 29 } 30 31 @H_673_72@for i @H_673_72@in index..<nums.count { 32 @H_673_72@var visited = visited 33 @H_673_72@if visited[i] == @H_673_72@true { 34 @H_673_72@conTinue 35 } @H_673_72@else { 36 visited[i] = @H_673_72@true 37 @H_673_72@if canPart(index:i,remain:remain,cursum: cursum + nums[i],visited: visited) { 38 @H_673_72@return @H_673_72@true 39 } 40 visited[i] = @H_673_72@false 41 } 42 } 43 44 @H_673_72@return @H_673_72@false 45 } 46 47 @H_673_72@return canPart(index:0,remain:k,cursum: 0,visited:[Int: Bool]()) 48 } 49 }
92ms
1 @H_673_72@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 @H_673_72@if nums.count == 0 && k == 0 { 5 @H_673_72@return @H_673_72@true 6 } 7 guard nums.count > 0,k > 0 @H_673_72@else { 8 @H_673_72@return @H_673_72@false 9 } 10 @H_673_72@var target = nums.reduce(0,+) 11 //Remember to check if the target can be fully divided by k 12 @H_673_72@if target % k != 0 { 13 @H_673_72@return @H_673_72@false 14 } 15 target = target/k 16 17 func canPart(index:Int,visited:[Int: Bool]) -> Bool { 18 @H_673_72@if remain == 0 { 19 @H_673_72@return @H_673_72@true 20 } 21 22 @H_673_72@if index == nums.count { 23 @H_673_72@return @H_673_72@false 24 } 25 26 @H_673_72@if cursum == target { 27 @H_673_72@return canPart(index: 0,remain: remain - 1,visited: visited) 28 } @H_673_72@else @H_673_72@if cursum > target { 29 @H_673_72@return @H_673_72@false 30 } 31 32 @H_673_72@for i @H_673_72@in index..<nums.count { 33 @H_673_72@var visited = visited 34 @H_673_72@if visited[i] == @H_673_72@true { 35 @H_673_72@conTinue 36 } 37 visited[i] = @H_673_72@true 38 @H_673_72@if canPart(index: i,remain: remain,visited: visited) { 39 @H_673_72@return @H_673_72@true 40 } 41 } 42 @H_673_72@return @H_673_72@false 43 } 44 @H_673_72@return canPart(index:0,visited:[Int: Bool]()) 45 } 46 }
96ms
1 @H_673_72@class Solution { 2 func canPartitionKSubsets(_ nums: [Int],_ k: int) -> Bool { 3 @H_673_72@var sum = 0 4 @H_673_72@for num @H_673_72@in nums { 5 sum += num 6 } 7 @H_673_72@if k <= 0 || sum % k != 0 { 8 @H_673_72@return @H_673_72@false 9 } 10 @H_673_72@var visited = Array(repeaTing: @H_673_72@false,count: nums.count) 11 @H_673_72@return canPartition(nums,&visited,k,sum / k) 12 } 13 14 @H_673_72@private func canPartition(_ nums: [Int],_ visited: inout [Bool],_ start_index: Int,_ k: Int,_ cur_sum: Int,_ cur_num: Int,_ target: int) -> Bool { 15 @H_673_72@if k == 1 { 16 @H_673_72@return @H_673_72@true 17 } 18 @H_673_72@if cur_sum == target && cur_num > 0 { 19 @H_673_72@return canPartition(nums,k - 1,0,target) 20 } 21 @H_673_72@for i @H_673_72@in start_index..<nums.count { 22 @H_673_72@if !visited[i] { 23 visited[i] = @H_673_72@true 24 let match = canPartition(nums,i + 1,cur_sum + nums[i],cur_num + 1,target) 25 @H_673_72@if match { 26 @H_673_72@return @H_673_72@true 27 } 28 visited[i] = @H_673_72@false 29 } 30 } 31 @H_673_72@return @H_673_72@false 32 } 33 }
1 @H_673_72@class Solution { 2 func canPartitionKSubsets(_ nums: [Int],_ k: int) -> Bool { 3 @H_673_72@var nums = nums 4 nums.sort() 5 @H_673_72@var sum:Int = nums.reduce(0,+) 6 @H_673_72@if sum % k != 0 {@H_673_72@return @H_673_72@false} 7 @H_673_72@var v:[Int] = [Int](repeaTing:0,count:k) 8 @H_673_72@return Helper(&nums,sum / k,&v,nums.count - 1) 9 } 10 11 func Helper(_ nums:inout [Int],_ target:Int,_ v:inout [Int],_ idx:int) -> Bool 12 { 13 @H_673_72@if idx == -1 14 { 15 @H_673_72@for t @H_673_72@in v 16 { 17 @H_673_72@if t != target {@H_673_72@return @H_673_72@false} 18 } 19 @H_673_72@return @H_673_72@true 20 } 21 @H_673_72@var num:Int = nums[idx] 22 @H_673_72@for i @H_673_72@in 0..<v.count 23 { 24 @H_673_72@if v[i] + num > target {@H_673_72@conTinue} 25 v[i] += num 26 @H_673_72@if Helper(&nums,target,idx - 1) 27 { 28 @H_673_72@return @H_673_72@true 29 } 30 v[i] -= num 31 } 32 @H_673_72@return @H_673_72@false 33 } 34 }
以上是大佬教程为你收集整理的[Swift]LeetCode698. 划分为k个相等的子集 | Partition to K Equal Sum Subsets全部内容，希望文章能够帮你解决[Swift]LeetCode698. 划分为k个相等的子集 | Partition to K Equal Sum Subsets所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。