刷题笔记day27-回溯算法3

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 "sort"var 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, i+1, curr-candidates[i], used)used[i] = false// 回溯if (len(path) > 0) {path = path[:len(path)-1]}}
}