leetcode40题如下
给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意:解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
**我的答案如下
**
package main
import (
"fmt"
"sort"
"strconv"
)
//leetcode40
func combinationSum2(candidates []int, target int) [][]int {
var res = make([][]int, 0)
sort.Ints(candidates)
var findSlice func(candidates []int, index, tmp int, tmpSlice []int)
findSlice = func(candidates []int, index, tmp int, tmpSlice []int) {
if index >= len(candidates) || tmp-candidates[index] < 0 {
return
}
tmp -= candidates[index]
tmpSlice = append(tmpSlice, candidates[index])
if tmp == 0 && !findFromRes(res, tmpSlice) {
targetSlice := make([]int, len(tmpSlice))
copy(targetSlice, tmpSlice)
res = append(res, targetSlice)
}
findSlice(candidates, index + 1, tmp, tmpSlice)
tmp += tmpSlice[len(tmpSlice)-1]
tmpSlice = tmpSlice[:len(tmpSlice)-1]
findSlice(candidates, index + 1, tmp, tmpSlice)
}
tmpslice := make([]int, 0)
findSlice(candidates, 0, target, tmpslice)
return res
}
func findFromRes(res [][]int, target []int) bool {
tmpMap := make(map[string]struct{})
for i := range res {
tmpStr := ""
for j := range res[i] {
tmpStr = tmpStr + strconv.Itoa(res[i][j]) + "-"
}
tmpMap[tmpStr] = struct{}{}
}
tmpStr := ""
for i := range target {
tmpStr = tmpStr + strconv.Itoa(target[i]) + "-"
}
_, ok := tmpMap[tmpStr]
return ok
}
func main() {
nums := []int{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
target := 30
res := combinationSum2(nums, target)
fmt.Print(len(res))
}
我的问题是:100多个用例都通过了,main函数中的这个用例无法通过,应该如何改代码?
给你推荐一个好地方,代码随想录,里面还有B站的视频解析
https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html#go