[Swift]LeetCode698. 划分为k个相等的子集 | Partition to K Equ
发布时间：2020-12-14 05:02:49 所属栏目：百科 来源：网络整理
导读：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 po
|
Given an array of integers? 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： 输入： nums = [4,k = 4 输出： True 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。? 注意:
16ms 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 partition 11 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 partition 34 return false 35 } 36 37 if k == 0 { 38 return true 39 } 40 41 if currentSum == expectedSum { 42 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 } else { 50 51 for i in numsIndex..<nums.count { 52 guard !isVisited[i] else { 53 // already used this number for a partition 54 continue 55 } 56 57 isVisited[i] = 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 if canPartition { 67 return true 68 } 69 70 isVisited[i] = false 71 } 72 } 73 74 return false 75 } 76 } 32ms 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 false 11 } 12 13 let sum = totalSum / k 14 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 false 23 } 24 25 if currentSum == sum { 26 27 if k == 1 { 28 return true 29 } 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 < sum 35 else { 36 37 for i in startIndex..<numbers.count { 38 let number = numbers[i] 39 40 if visited[i] { 41 continue 42 } 43 44 visited[i] = true 45 46 if canPartitionKSubsets(numbers: numbers,startIndex: i+1,currentSum: currentSum + number,visited: &visited) { 47 return true 48 } 49 50 visited[i] = false 51 } 52 } 53 54 return false 55 } 56 } 60ms 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 cached 19 } 20 let allElementBitSet = (1<<nums.count) - 1 21 if bitset == allElementBitSet && remainingInBucket == bucketTarget { 22 // All elements are set and all buckets are filled. 23 return true 24 } 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 bucket 31 } 32 if canPartitionSubsets( 33 nums,34 bitset | (1<<i),35 updatedRemainingInBucket,36 bucketTarget,37 &cache) { 38 cache[bitset] = true 39 return true 40 } 41 } 42 cache[bitset] = false 43 return false 44 } 45 } 88ms 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 false 12 } 13 target = target/k 14 15 16 func canPart(index:Int,remain:Int,curSum: Int,visited:[Int: Bool]) -> Bool { 17 if remain == 0 { 18 return true 19 } 20 21 if index == nums.count { 22 return false 23 } 24 25 if curSum == target { 26 return canPart(index:0,remain:remain - 1,curSum:0,visited:visited) 27 } else if curSum > target { 28 return false 29 } 30 31 for i in index..<nums.count { 32 var visited = visited 33 if visited[i] == true { 34 continue 35 } else { 36 visited[i] = true 37 if canPart(index:i,remain:remain,curSum: curSum + nums[i],visited: visited) { 38 return true 39 } 40 visited[i] = false 41 } 42 } 43 44 return false 45 } 46 47 return canPart(index:0,remain:k,curSum: 0,visited:[Int: Bool]()) 48 } 49 } 92ms 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 k 12 if target % k != 0 { 13 return false 14 } 15 target = target/k 16 17 func canPart(index:Int,visited:[Int: Bool]) -> Bool { 18 if remain == 0 { 19 return true 20 } 21 22 if index == nums.count { 23 return false 24 } 25 26 if curSum == target { 27 return canPart(index: 0,remain: remain - 1,visited: visited) 28 } else if curSum > target { 29 return false 30 } 31 32 for i in index..<nums.count { 33 var visited = visited 34 if visited[i] == true { 35 continue 36 } 37 visited[i] = true 38 if canPart(index: i,remain: remain,visited: visited) { 39 return true 40 } 41 } 42 return false 43 } 44 return canPart(index:0,visited:[Int: Bool]()) 45 } 46 } 96ms 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 true 17 } 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] = true 24 let match = canPartition(nums,i + 1,cur_sum + nums[i],cur_num + 1,target) 25 if match { 26 return true 27 } 28 visited[i] = false 29 } 30 } 31 return false 32 } 33 }
Runtime:?244 ms
Memory Usage:?19.1 MB
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) -> Bool 12 { 13 if idx == -1 14 { 15 for t in v 16 { 17 if t != target {return false} 18 } 19 return true 20 } 21 var num:Int = nums[idx] 22 for i in 0..<v.count 23 { 24 if v[i] + num > target {continue} 25 v[i] += num 26 if helper(&nums,target,idx - 1) 27 { 28 return true 29 } 30 v[i] -= num 31 } 32 return false 33 } 34 } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |