[Swift]LeetCode77.组合|Combinations

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

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

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

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

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

注：博主将坚持每月上线一个新app！！！

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

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

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:

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

32ms

 1 class Solution {
 2     
 3     func combine(_ n: Int, _ k: Int) -> [[Int]] {
 4         guard n > 0 else {
 5             return []
 6         }
 7         var result : [[Int]] = []
 8         var nums : [Int] = Array(repeating: 0, count: k)
 9         combineNext(lastIndex: 1,leftCount: k, numsIndex: 0, result: &result, nums: &nums, maxN: n)
10         return result
11     }
12     private func combineNext(lastIndex:Int,leftCount:Int,numsIndex:Int , result : inout  [[Int]] , nums : inout [Int] , maxN : Int) {
13         if leftCount == 0{
14             result.append(nums)
15             return
16         }
17         if lastIndex>maxN {
18             return
19         }
20             
21         for idx in lastIndex...(maxN-leftCount+1) {
22             nums[numsIndex] = idx
23             combineNext(lastIndex: idx+1, leftCount: leftCount-1,numsIndex: numsIndex+1, result: &result, nums: &nums, maxN: maxN)
24         }
25     }
26 }

36ms

 1 class Solution {
 2     
 3     func combine(_ n: Int, _ k: Int) -> [[Int]] {
 4         guard n > 0 else {
 5             return []
 6         }
 7         var result = [[Int]]()
 8         helper(1, n, k, [Int](), &result)
 9         return result
10     }
11     
12     func helper(_ start: Int, _ end: Int, _ k: Int, _ added: [Int], _ result: inout [[Int]]) {
13         if k == 0 {
14             result.append(added)
15             return
16         }   
17         
18         for i in start...(end-k+1) {
19             var tempAdded = added
20             tempAdded.append(i)
21             helper(i+1, end, k-1, tempAdded, &result)
22         }
23     }
24 }

40ms

 1 class Solution {
 2     func combineHelper(withResult result: inout [[Int]], usingTemp temp: inout [Int], andStart start: Int, andN n: Int, andK k: Int) {
 3         
 4         if (k <= 0) {
 5             result.append(temp)
 6             return
 7         }
 8         
 9         for i in start...n {
10             if (n - i + 1) >= k {
11                 temp.append(i)
12                 combineHelper(withResult: &result, usingTemp: &temp, andStart: i + 1, andN: n, andK: k - 1)
13                 temp.removeLast()
14             }
15         }
16     }
17     
18     func combine(_ n: Int, _ k: Int) -> [[Int]] {
19         var result = [[Int]]();
20         var temp = [Int]()
21         combineHelper(withResult: &result, usingTemp: &temp, andStart: 1, andN: n, andK: k)
22         return result
23     }
24 }

48ms

 1 class Solution {
 2     
 3     func combine(_ n: Int, _ k: Int) -> [[Int]] {
 4         guard n > 0 else {
 5             return []
 6         }
 7         var result = [[Int]]()
 8         helper(1, n, k, [Int](), &result)
 9         return result
10     }
11     
12     func helper(_ start: Int, _ end: Int, _ k: Int, _ added: [Int], _ result: inout [[Int]]) {
13         if k == 0 {
14             result.append(added)
15         }
16         
17         if start > end {
18             return
19         }      
20         
21         for i in start...(end-k+1) {
22             var tempAdded = added
23             tempAdded.append(i)
24             helper(i+1, end, k-1, tempAdded, &result)
25         }
26     }

68ms

 1 class Solution {
 2     func combine(_ n: Int, _ k: Int) -> [[Int]] {
 3         if n < k {
 4             return []
 5         }
 6         var combo: [Int] = []
 7         var results: [[Int]] = []
 8         for i in 1...n {
 9             backtacking(i, n, k, &combo, &results)
10         }
11         return results
12     }
13     
14     private func backtacking(_ begin: Int, _ end: Int, _ limit: Int, _ combo: inout [Int], _ results: inout [[Int]]) {
15         let remains = end - begin + 1
16         if combo.count + remains >= limit {
17             combo.append(begin)
18             if combo.count == limit {
19                 results.append(combo)
20             } else {
21                 for i in 1..<remains {
22                     backtacking(begin + i, end, limit, &combo, &results)
23                 }
24             }
25             combo.removeLast()
26         }
27     }
28 }

116ms

 1 class Solution {
 2     
 3     func combine(_ n: Int, _ k: Int) -> [[Int]] {
 4         guard n > 0 else {
 5             return []
 6         }
 7         var result : [[Int]] = []
 8         var nums : [Int] = Array(repeating: 0, count: k)
 9         combineNext(lastIndex: 1,leftCount: k, numsIndex: 0, result: &result, nums: &nums, maxN: n)
10         return result
11     }
12     private func combineNext(lastIndex:Int,leftCount:Int,numsIndex:Int , result : inout  [[Int]] , nums : inout [Int] , maxN : Int) {
13         if leftCount == 0{
14             result.append(nums)
15             return
16         }
17         if lastIndex>maxN {
18             return
19         }
20             
21         for idx in lastIndex...maxN {
22             nums[numsIndex] = idx
23             combineNext(lastIndex: idx+1, leftCount: leftCount-1,numsIndex: numsIndex+1, result: &result, nums: &nums, maxN: maxN)
24         }
25     }
26 }

204ms

1 class Solution {
2     func combine(_ n: Int, _ k: Int) -> [[Int]] {
3         guard k <= n else { return [] }
4         guard k > 0 else { return [[]] }
5         guard k > 1 else { return (1...n).map { [$0] } }
6 
7         return combine(n-1, k) + combine(n-1, k-1).map { $0 + [n] }
8     }
9 }

152ms

 1 class Solution {
 2     var list:[[Int]] = [[Int]]()
 3     var n:Int = 0
 4     func combine(_ n: Int, _ k: Int) -> [[Int]] {
 5         self.n = n
 6         var comb:[Int] = [Int]()
 7         combines(comb,1, k)
 8         return list
 9     }
10     
11     func combines(_ temp:[Int],_ count:Int,_ k:Int)
12     {
13         var temp = temp
14         if k == 0
15         {
16             list.append(temp)
17             return
18         }
19         if count + k - 1 > n { return}
20         temp.append(count)
21         combines(temp, count + 1, k - 1)
22         temp.removeLast()
23         combines(temp, count + 1, k)
24     }
25 }