爱做网站免费版,抖音代运营公司加盟,为什么做网站结构优化,室内装修公司排行39. 组合总和 var path []int
var tmp []int
var result [][]int// 还是需要去重复#xff0c;题目中要求的是至少一个数字备选的数量不同。
// 所以需要剪枝操作#xff0c;右边的要比左边的
func combinationSum(candidates []int, target int) [][]int {// 组合问题pa…39. 组合总和 var path []int
var tmp []int
var result [][]int// 还是需要去重复题目中要求的是至少一个数字备选的数量不同。
// 所以需要剪枝操作右边的要比左边的
func combinationSum(candidates []int, target int) [][]int {// 组合问题path []int{}result [][]int{}nfs(candidates, target, 0)return result
}func nfs(candidates []int, curr, startIndex int) bool {// 终止条件if curr 0 {tmp make([]int, len(path))copy(tmp, path)result append(result, tmp)return true} else if curr 0 {return false}for i : startIndex; i len(candidates); i {// 去重右边的比左边的大的情况才继续,startIndexpath append(path, candidates[i])// nfsnfs(candidates, curr-candidates[i], i)if len(path) 0 {path path[:len(path)-1]}}return true
}40. 组合总和 II ⭐️⭐️⭐️
这个题很重点 关键点
一个组内可以允许重复但是不同组不可以是重复的
涉及到是同一层是否重复就是不同组还是某一个树枝是否重复同一组内。 所以这样就很清晰了。 我们可以用一个 used 数组如果used[i] true说明在一个同一个树枝上使用了。 // 去除相邻重复 // used[i-1] true 说明在同一树枝上使用了 // used[i-1] false说明不是同一树枝此时如果candidates[i] candidates[i-1] import sortvar path []int
var result [][]intfunc combinationSum2(candidates []int, target int) [][]int {// 这个是给定一个数组了在里面挑选。// 我的思路就是先排序在递归// 还有一种情况111435, 这个重复值在第二次就不应该再用了path []int{}result [][]int{}sort.Ints(candidates)used : make([]bool, len(candidates))nfs(candidates, 0, target, used)return result
}func nfs(candidates []int, startIndex, curr int, used []bool) {// 终止条件if (curr 0) {result append(result, append([]int{}, path...))return } else if (curr 0) {return }// 循环for i : startIndex; i len(candidates); i {// 去除相邻重复// used[i-1] true 说明在同一树枝上使用了// used[i-1] false说明不是同一树枝此时如果candidates[i] candidates[i-1]// 那么就跳过if i 0 candidates[i] candidates[i-1] used[i-1] false {continue}used[i] truepath append(path, candidates[i])nfs(candidates, i1, curr-candidates[i], used)used[i] false// 回溯if (len(path) 0) {path path[:len(path)-1]}}
}
