给定一个候选数字数组 (C) (不含重复项) 和目标数字 (T),在 C 中找到所有唯一的组合,使得组合中的数之和为 T。
C 中的同一个数字可以无限制重复使用。
注意:
- 所有数字,包括目标数字,都是正数
- 结果数组中不能包含重复的组合
例如:给定一个候选数组: [2, 3, 6, 7] 和 目标数字 7,
结果数组如下:
```
[
[7],
[2, 2, 3]
]
```
Go 函数签名如下:
```go
func combinationSum(candidates []int, target int) [][]int {
}
```
```go
func combinationSum(candidates []int, target int) [][]int {
sort.Ints(candidates)
record := []int{}
resultChan := make(chan [][]int)
go forkJoin(candidates, target, record, resultChan)
result := <-resultChan
result = unique(result)
return result
}
func forkJoin(candidates []int, target int, record []int, resultChan chan [][]int) {
result := make([][]int, 0)
defer func() {
resultChan <- result
}()
if len(candidates) == 0 {
if target == 0 {
result = append(result, record)
}
return
}
resultChanArr := make([]chan [][]int, 0)
for _, v := range candidates {
middleTarget := target - v
middleIndex := seekIndex(candidates, middleTarget)
middleRecord := append(record, v)
middleResultChan := make(chan [][]int)
resultChanArr = append(resultChanArr, middleResultChan)
go forkJoin(candidates[0:middleIndex], middleTarget, middleRecord, middleResultChan)
}
for _, middleResultChan := range resultChanArr {
middleResult := <-middleResultChan
if len(middleResult) != 0 {
for _, middleResultRow := range middleResult {
result = append(result, middleResultRow)
}
}
}
}
func seekIndex(candidates []int, middleTarget int) int {
for i, v := range candidates {
if middleTarget < v {
return i
}
}
return len(candidates)
}
func unique(src [][]int) [][]int {
tgt := make([][]int, 0)
for _, v := range src {
ok := true
for i := 0; i < len(v)-1; i++ {
if v[i] > v[i+1] {
ok = false
break
}
}
if ok {
tgt = append(tgt, v)
}
}
return tgt
}
```
#3