大佬教程收集整理的这篇文章主要介绍了[Swift]LeetCode216. 组合总和 III | Combination Sum III,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
Find all possible combinations of k numbers that add up to a number n,given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Note:
Example 1:
Input: k = 3,n = 7 Output: [[1,2,4]]
Example 2:
Input: k = 3,n = 9 Output: [[1,6],[1,3,5],[2,4]]
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
说明:
示例 1:
输入: k = 3,n = 7 输出: [[1,4]]
示例 2:
输入: k = 3,n = 9 输出: [[1,4]]
8ms
1 class Solution { 2 func combinationSum3(_ k: Int,_ n: int) -> [[Int]] { 3 guard k > 0,n > 0 else { 4 return [[Int]]() 5 } 6 7 var result = [[Int]]() 8 9 func dfs(index:Int,target:Int,path:[Int]) { 10 if target == 0 && path.count == k { 11 result.append(path) 12 return 13 } else if target < 0 || index > 9 || path.count >= k { 14 return 15 } 16 17 for i in index...9 { 18 dfs(index:i + 1,target: target - i,path:path + [i]) 19 } 20 } 21 dfs(index:1,target:n,path:[Int]()) 22 23 return result 24 } 25 }
12ms
1 class Solution { 2 func combinationSum3(_ k: Int,_ n: int) -> [[Int]] { 3 var res = [[Int]]() 4 var temp = [Int]() 5 dfs(&res,&temp,n,k,1) 6 return res 7 } 8 9 private func dfs(_ res: inout [[Int]],_ temp: inout [Int],_ n: Int,_ k: Int,_ index: int) { 10 if n == 0 && k == 0 { 11 res.append(Array(temp)) 12 return 13 } 14 if n <= 0 || k == 0 || index > 9 { 15 return 16 } 17 for i in index...9 { 18 temp.append(i) 19 dfs(&res,n - i,k - 1,i + 1) 20 temp.removeLast() 21 } 22 } 23 }
12ms
1 class Solution { 2 func combinationSum3(_ k: Int,_ n: int) -> [[Int]] { 3 var res = [Set<Int>]() 4 var cur = Set<Int>() 5 let nums : Set<Int> = [1,2,3,4,5,6,7,8,9] 6 sumHelp(k,&cur,&res,nums) 7 8 return res.map{Array($0)} 9 } 10 11 func sumHelp(_ k : Int,_ n : Int,_ cur : inout Set<Int>,_ res : inout [Set<Int>],_ nums : Set<Int>) { 12 if k == 1 { 13 if nums.contains(n) && !cur.contains(n) { 14 cur.insert(n) 15 res.append(cur) 16 cur.remove(n) 17 } 18 }else { 19 for i in nums where i * 2 < n && i > cur.max() ?? 0 { 20 cur.insert(i) 21 var set = nums 22 set.remove(i) 23 sumHelp(k - 1,&res,set) 24 cur.remove(i) 25 } 26 } 27 } 28 }
16ms
1 class@H_815_502@ Solution { 2 func combinationSum3(_ k: Int,_ n: int) ->@H_815_502@ [[Int]] { 3 var array =@H_815_502@ [Int]() 4 for i in 1 ... 9@H_815_502@ { 5 @H_815_502@ array.append(i) 6 @H_815_502@ } 7 8 var result =@H_815_502@ [[Int]]() 9 10 @H_815_502@ func Helper(remain: [Int],current: [Int],sum: int) { 11 var newRemain =@H_815_502@ remain 12 while newRemain.count > 0@H_815_502@ { 13 let temp =@H_815_502@ newRemain.removeFirst() 14 var newCurrent =@H_815_502@ current 15 @H_815_502@ newCurrent.append(temp) 16 let newSum = sum +@H_815_502@ temp 17 if newSum == n && newCurrent.count ==@H_815_502@ k { 18 @H_815_502@ result.append(newCurrent) 19 } else if newSum >@H_815_502@ n { 20 conTinue 21 } else@H_815_502@ { 22 @H_815_502@ Helper(remain: newRemain,current: newCurrent,sum: newSum) 23 @H_815_502@ } 24 @H_815_502@ } 25 @H_815_502@ } 26 27 Helper(remain: array,current: [Int](),sum: 0@H_815_502@) 28 return@H_815_502@ result 29 @H_815_502@ } 30 }
20ms
1 import Foundation 2 3 class Solution { 4 func combinationSum3(_ k: Int,_ n: int) -> [[Int]] { 5 var cacheMap = [String: [[Int]]]() 6 return createConbination(count: k,target: n,prefix: [Int](),cacheMap: &cacheMap) 7 } 8 9 func createConbination(count: Int,target: Int,prefix: [Int],cacheMap: inout [String: [[Int]]]) -> [[Int]] { 10 if count == 0 || target == 0 { 11 return [prefix] 12 } 13 14 15 var minValue = 1 16 if let lastnumber = prefix.last { 17 minValue = lastnumber + 1 18 } 19 minValue = max(minValue,target - 9 * (count - 1)) 20 let maxValue = min(9,target - (count - 1)) 21 if minValue > maxValue { 22 return [[Int]]() 23 } 24 25 let key = String(format: "%d_%d_%d",count,target,minvalue) 26 if let cachedValue = cacheMap[key] { 27 var output = [[Int]]() 28 for sequence in cachedValue { 29 var newSequence = prefix 30 let lasTindex = sequence.count - 1 31 let suffix = sequence[lasTindex - count + 1...lasTindex] 32 newSequence.append(contentsOf: suffiX) 33 output.append(newSequencE) 34 } 35 return output 36 } 37 38 var output = [[Int]]() 39 for num in minValue...maxValue { 40 var newPrefix = prefix 41 newPrefix.append(num) 42 let newArray = createConbination(count: count - 1,target: target - num,prefix: newPrefix,cacheMap: &cacheMap) 43 output.append(contentsOf: newArray) 44 } 45 46 cacheMap[key] = output 47 return output 48 } 49 }
24ms
1 class Solution { 2 func combinationSum3(_ k: Int,_ n: int) -> [[Int]] { 3 var result: [[Int]] = [] 4 combinationSum3(k,[],1,&result) 5 return result 6 } 7 8 func combinationSum3(_ k: Int,_ remain: Int,_ nums: [Int],_ index: Int,_ result: inout [[Int]]) { 9 if nums.count > k || remain < 0 { 10 return 11 } 12 13 if nums.count == k && remain == 0 { 14 result.append(nums) 15 return 16 } 17 18 let loopCount = min(remain,9) 19 if index > loopCount { 20 return 21 } 22 23 var nums = nums 24 for num in index...loopCount { 25 nums.append(num) 26 combinationSum3(k,remain - num,nums,num + 1,&result) 27 nums.removeLast() 28 } 29 } 30 }
以上是大佬教程为你收集整理的[Swift]LeetCode216. 组合总和 III | Combination Sum III全部内容,希望文章能够帮你解决[Swift]LeetCode216. 组合总和 III | Combination Sum III所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。