[Swift]LeetCode216. 组合总和 III | Combination Sum III_app

概述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: All numbers will be @H_403_0@ @H_403_0@

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:

All numbers will be positive integers. The solution set must not contain duplicate combinations.

Example 1:

input: k = 3,n = 7Output: [[1,2,4]]

Example 2:

input: k = 3,n = 9Output: [[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                 return13             } 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 result24     }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             return13         }14         if n <= 0 || k == 0 || index > 9  {15             return16         }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 = nums22                 set.remove(i)23                 sumHelp(k - 1,&res,set)24                 cur.remove(i)25             }26         }27     }28 }

16ms

 1 class@H_606_502@ Solution { 2     func combinationSum3(_ k: Int,_ n: Int) ->@H_606_502@ [[Int]] { 3 var array =@H_606_502@ [Int]() 4 for i in 1 ... 9@H_606_502@ { 5 @H_606_502@ array.append(i) 6 @H_606_502@ } 7 8 var result =@H_606_502@ [[Int]]() 9 10 @H_606_502@ func helper(remain: [Int],current: [Int],sum: Int) { 11 var newRemain =@H_606_502@ remain 12 while newRemain.count > 0@H_606_502@ { 13 let temp =@H_606_502@ newRemain.removeFirst() 14 var newCurrent =@H_606_502@ current 15 @H_606_502@ newCurrent.append(temp) 16 let newSum = sum +@H_606_502@ temp 17 if newSum == n && newCurrent.count ==@H_606_502@ k { 18 @H_606_502@ result.append(newCurrent) 19 } else if newSum >@H_606_502@ n { 20 continue 21 } else@H_606_502@ { 22 @H_606_502@ helper(remain: newRemain,current: newCurrent,sum: newSum) 23 @H_606_502@ } 24 @H_606_502@ } 25 @H_606_502@ } 26 27 helper(remain: array,current: [Int](),sum: 0@H_606_502@) 28 return@H_606_502@ result 29 @H_606_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 = 116     if let lastNumber = prefix.last {17       minValue = lastNumber + 118     }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 = prefix30         let lastIndex = sequence.count - 131         let suffix = sequence[lastIndex - count + 1...lastIndex]32         newSequence.append(contentsOf: suffix)33         output.append(newSequence)34       }35       return output36     }37 38     var output = [[Int]]()39     for num in minValue...maxValue {40       var newPrefix = prefix41       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] = output47     return output48   }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             return11         }12 13         if nums.count == k && remain == 0 {14             result.append(nums)15             return16         }17         18         let loopCount = min(remain,9)19         if index > loopCount {20             return21         }22 23         var nums = nums24         for num in index...loopCount {25             nums.append(num)26             combinationSum3(k,remain - num,nums,num + 1,&result)27             nums.removeLast()28         }29     }30 }