[Swift]LeetCode216.组合总和III|CombinationSumIII

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10198008.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新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 positive integers.
The solution set must not contain duplicate combinations.

Example 1:

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

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,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, &temp, 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, n, &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, n - i, &cur, &res, set)
24                 cur.remove(i)
25             }
26         }
27     }
28 }

16ms

 1 class Solution {
 2     func combinationSum3(_ k: Int, _ n: Int) -> [[Int]] {
 3         var array = [Int]()
 4         for i in 1 ... 9 {
 5             array.append(i)
 6         }
 7         
 8         var result = [[Int]]()
 9         
10         func helper(remain: [Int], current: [Int], sum: Int) {
11             var newRemain = remain
12             while newRemain.count > 0 {
13                 let temp = newRemain.removeFirst()
14                 var newCurrent = current
15                 newCurrent.append(temp)
16                 let newSum = sum + temp
17                 if newSum == n && newCurrent.count == k {
18                     result.append(newCurrent)
19                 } else if newSum > n {
20                     continue
21                 } else {
22                     helper(remain: newRemain, current: newCurrent, sum: newSum)
23                 }
24             }
25         }
26         
27         helper(remain: array, current: [Int](), sum: 0)
28         return result
29     }
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, n, [], 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 }