[Swift]LeetCode216. 组合总和 III | Combination Sum III
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10198008.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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 }