39 组合总和
func combinationSum(candidates []int, target int) [][]int {
// 思路，组合问题考虑回溯算法，考虑到元素可能重复问题，所以，树的最大深度应该是target / min(candudates) + 1
var path = []int{}
var res = [][]int{}
backtracking(target, candidates, &path, &res)
return res
}
func backtracking(target int, li []int, path *[]int, res *[][]int){
// 递归/回溯终止条件，收集结果
if sum(*path) == target {
var copypath = make([]int, len(*path))
copy(copypath, *path)
*res = append(*res, copypath)
return
}
// 剪枝，如果路径和大于target，不再递归回溯
if sum(*path) > target {
return
}
// 递归回溯
for i:=0; i<len(li); i++ {
*path = append(*path, li[i])
backtracking(target, li[i : ], path, res)
*path = (*path)[0 : len(*path) - 1]
}
return
}
func sum(li []int) int {
var sum int
for _, l := range li {
sum += l
}
return sum
}
40 组合之和2
go语言允许切片的区间取值li[start : end], start == end == len(li) 这种语法是正确的，但是li[len(li)] 这种索引取值会报错out of range
func combinationSum2(candidates []int, target int) [][]int {
// 思路，组合问题考虑回溯算法
var path = []int{}
var res = [][]int{}
candidates = quicksort(candidates)
backtracking(target, candidates, &path, &res)
return res
}
func backtracking(target int, li []int, path *[]int, res *[][]int){
if sum(*path) == target {
var copypath = make([]int, len(*path))
copy(copypath, *path)
*res = append(*res, copypath)
return
}
// 剪枝，如果路径和大于target，不再递归回溯
if sum(*path) > target {
return
}
for i:=0; i<len(li); i++ {
// 处理重复元素情况
if i > 0 && li[i - 1] == li[i] {
// 元素重复，那么第二个元素结果集必然包含在第一个元素结果集中
continue
}
*path = append(*path, li[i])
backtracking(target, li[i+1 : ], path, res) // 不能重复，那就传入数组的时候不包含首元素就行了 !!! tmd li[start: end] start == end == len(li), 这样语法居然不会报错，活久见
*path = (*path)[0 : len(*path) - 1]
}
return
}
func sum(li []int) int {
var sum int
for _, l := range li {
sum += l
}
return sum
}
func quicksort(li []int) []int {
// 取首位作为中值，划分大于中值区间和小于中值区间，然后递归
if len(li) == 0{
return nil
}
pivot := li[0]
var left, right, mid []int
for _, l := range li {
if l > pivot {
right = append(right, l)
}else if l < pivot{
left = append(left, l)
}else {
mid = append(mid, l)
}
}
left = quicksort(left)
right = quicksort(right)
return append(left, append(mid, right...)...)
}
131 分割回文串
func partition(s string) [][]string {
// 基础的回溯收集思路，外加一个判断回文串的函数
var path = []string{}
var res = [][]string{}
backtracking(s, 0, &path, &res)
return res
}
func backtracking(s string, div int, path *[]string, res *[][]string) { // div 切割位置
if div == len(s) { // 遇到叶子节点，说明此时path元素已经全是回文，收集到结果集中
var copypath = make([]string, len(*path))
copy(copypath, *path)
*res = append(*res, copypath)
return
}
for i:=div; i<len(s); i++{
if recoverStr(s[div: i+1]){
*path = append(*path, s[div: i+1])
backtracking(s, i+1, path, res)
*path = (*path)[0 : len(*path) - 1]
}else {
continue // 剪枝本层的该节点以及对应子树
}
}
return
}
func recoverStr(s string) bool {
if len(s) == 0{
return false
}
if len(s) == 1{
return true
}
left := 0
right := len(s) - 1
for left < right {
if s[left] == s[right] {
left++
right--
}else {
return false
}
}
return true
}
// 此题理解不深刻
指针path *[]int 添加到指针 res *[][]int 产生的思考
func backtracking(s string, path *[]byte, res *[]string) {
if recover(*path) {
*res = append(*res, string(*path)) // string(*path) 相当于隐式创建了一个string变量，用来存储
return
}
...
}
func backtracking2(s string, path *[]int, res *[][]int) {
if recover(*path) {
*res = append(*res, *path)
return
}
...
}
func backtracking3(s string, path *[]int, res *[][]int) {
if recover(*path) {
var copypath []int
copy(copypath, *path)
*res = append(*res, copypath)
return
}
...
}
// 上面三种写法保存结果集，其中1，3是正确的，2是错误的，对于收集的同样长度的结果集，所有结果都是重复的，并且等于最后收集的结果
// 切片在go中是有三个数据的结果，1，指向底层数组的指针 2，切片长度 3，切片容量
// 对于指针类型的引用，path代表的是指向底层数组的指针，*path代表的是底层数组，所以，res append操作，每一个元素指向的也是*path的底层数组
// 如果对于同一个长度的数组，我们在回溯[1,2,3] 回溯[3] 添加[4], 由于没有改变底层数组的长度，所以，go没有开辟新的存储空间并指向新的底层数组，所以我们的修改都是基于原有的底层数组之上，这样导致我们这边的修改，会对res中以及保存的指向相同底层数组的结果集发生修改。所以我们需要对*path进行赋值到其他变量，用来指向不同的空间，以用来避免底层修改产生的连锁反应
// 另一个方面，可以预见到的是，如果*path = []int{1}, res append, *path=append(..., 2), res append, 这种情况，res不会被修改，因为，path切片扩容了会开辟新的内存空间，并把原来的切片值放入新空间，但是res指向的还是原来的底层数组，不会发生改变