[Swift]LeetCode39. 组合总和 | Combination Sum

发布时间：2020-12-14 05:10:30 所属栏目：百科来源：网络整理

导读：Given a?set?of candidate numbers ( candidates )?(without duplicates)?and a target number ( target ),find all unique combinations in? candidates ?where the candidate numbers sums to? target . The?same?repeated number may be chosen from? can

Given a?set?of candidate numbers (candidates)?(without duplicates)?and a target number (target),find all unique combinations in?candidates?where the candidate numbers sums to?target.

The?same?repeated number may be chosen from?candidates?unlimited number of times.

Note:

All numbers (including?target) will be positive integers.
The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = target =,A solution set is:
[
  [7],[2,2,3]
]
[2,3,6,7],7

Example 2:

Input: candidates = [2,5]target = 8,A solution set is:
[
? [2,2],? [2,3],? [3,5]
],

给定一个无重复元素的数组?candidates?和一个目标数?target?，找出?candidates?中所有可以使数字和为?target?的组合。

candidates?中的数字可以无限制重复被选取。

说明：

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

示例?1:

输入: candidates = target =,所求解集为:
[
  [7],7

示例?2:

输入: candidates = [2,所求解集为:
[
? [2,

20ms

 1 class Solution {
 2     var result = [[Int]]()
 3     func combinationSum(_ candidates: [Int],_ target: Int) -> [[Int]] {
 4         combinationSum(candidates,target,0,[Int]())
 5         return result
 6     }
 7     
 8     func combinationSum(_ candidates: [Int],_ target: Int,_ currentInex: Int,_ usdedNums: [Int]) {
 9         if target <= 0  {
10             if target == 0 {
11                 result.append(usdedNums)               
12             }
13             return
14         }
15         for i in currentInex..<candidates.count {
16             let currentValue = candidates[i]
17             if currentValue > target {
18                 continue
19             }
20             var usdedNumsCopy = usdedNums
21             usdedNumsCopy.append(currentValue)
22             combinationSum(candidates,target-currentValue,i,usdedNumsCopy)
23         }
24     }
25 }

24ms

 1 class Solution {
 2     func combinationSum(_ candidates: [Int],_ target: Int) -> [[Int]] {
 3         let candidatesCopy = candidates.sorted{ $0 < $1 }
 4         var tmp = [Int]()
 5         var res = [[Int]]()
 6         var index = 0
 7         helper(&tmp,&res,index,candidatesCopy,target)
 8         return res
 9     }
10     
11     private func helper(_ tmp: inout [Int],_ res: inout [[Int]],_ index: Int,_ candidatesCopy: [Int],_ target: Int) {
12         if target == 0 {
13             res.append(tmp)
14             return
15         }else if index == candidatesCopy.count {
16             return
17         }
18         
19         for i in index..<candidatesCopy.count {
20             if candidatesCopy[i] > target {
21                 return
22             }else if i != index && candidatesCopy[i] == candidatesCopy[i - 1] {
23                 continue
24             }
25             
26             tmp.append(candidatesCopy[i])
27             helper(&tmp,&res,target - candidatesCopy[i])
28             tmp.removeLast()
29         }
30     }
31 }

28ms

 1 class Solution {
 2     func combinationSum(_ candidates: [Int],_ target: Int) -> [[Int]] {
 3         var result = [[Int]]()
 4         var out = [Int]()
 5         var candidates = candidates.sorted()
 6         combinationSumDFS(candidates,0,&out,&result)
 7         return result
 8     }
 9     
10     func combinationSumDFS(_ candidates: [Int],_ start: Int,_ out: inout [Int],_ res: inout [[Int]]) {
11         if target == 0 {
12             res.append(out)
13         } else {
14             for i in start..<candidates.count {
15                 guard target - candidates[i] >= 0 else {
16                     break
17                 }
18                 out.append(candidates[i])
19                 combinationSumDFS(candidates,target - candidates[i],&res)
20                 out.remove(at: out.count - 1)
21                 
22             }
23         }
24     }
25     
26 }

28ms

 1 class Solution {
 2     
 3     var list = [[Int]]()
 4     
 5     func combinationSum(_ candidates: [Int],_ target: Int) -> [[Int]] {
 6         var currentlySelected = [Int]()
 7         recursiveCombSum(candidates: candidates,index: 0,target: target,currentlySelected: currentlySelected)
 8         return list
 9     }
10     
11     func recursiveCombSum(candidates: [Int],index: Int,target: Int,currentlySelected: [Int]) {
12         if 0 == target {
13             list += [currentlySelected]
14         }
15         if index == candidates.count {
16         } else {
17             for i in index..<candidates.count {
18                 if candidates[i] <= target {
19                     var newTarget = target - candidates[i]
20                     var newList = currentlySelected + [candidates[i]]
21                     recursiveCombSum(candidates: candidates,index: i,target: newTarget,currentlySelected: newList)
22                 }
23             }
24         }
25     }
26 }

56ms

 1 class Solution {
 2     var conbineArray = [[Int]]()
 3     func combinationSum(_ candidates: [Int],_ target: Int) -> [[Int]] {
 4         let count = candidates.count
 5         guard count > 0 else {
 6             return [[Int]]()
 7         }
 8         combine(candidates,[Int](),count,target)
 9         return conbineArray
10     }
11     
12     func combine(_ candidates: [Int],_ currentCombine: [Int],_ count: Int,_ target: Int) {
13         if target < 0 { return }
14         if index == count { return }
15         if target == 0 {
16             conbineArray.append(currentCombine)
17             return
18         }
19         
20         combine(candidates,currentCombine,index + 1,target)
21         var currentCombine = currentCombine
22         currentCombine.append(candidates[index])
23         combine(candidates,target - candidates[index])
24     }
25 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!