带路径的递归 VS. 不带路径的递归
- 带路径的递归：回溯，前 4 个题
- 不带路径的递归：大部分 dp，状态压缩 dp 认为是路径简化了结构，dp 专题后续讲述
任何递归都是 dfs（深度优先搜索）且非常灵活。回溯这个术语并不重要。
题目1.返回字符串全部子序列，子序列要求去重
题目描述
子序列：每一个位置要或不要，子序列不要求连续（区别于子串）
子序列本身是可以有重复的，只是这个题目要求去重
测试链接
答案
package main
const (
MAXN = 17
)
var (
S string
n int
path = [MAXN]byte{}
set map[string]struct{} // 用于去重
emptyStruct = struct{}{}
)
/**
* @param s string字符串
* @return string字符串一维数组
*/
func generatePermutation(s string) []string {
S = s
n = len(s)
// 牛客 go 版本太低，没有 clear 方法，只能重新建一个了
// clear(set)
set = map[string]struct{}{}
backtracking(0, 0)
ans := make([]string, 0, len(set))
for str := range set {
ans = append(ans, str)
}
return ans
}
func backtracking(sIdx, pathIdx int) {
set[string(path[:pathIdx])] = emptyStruct
if sIdx == n {
return
}
path[pathIdx] = S[sIdx]
backtracking(sIdx+1, pathIdx+1)
backtracking(sIdx+1, pathIdx)
}复杂度 ^1
时间复杂度：
子序列共 个，每个子序列长度平均为 ，即生成一个需要
题目2.返回数组的所有组合，可以无视元素顺序
题目描述
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
测试链接
思路
答案
复杂度
时间复杂度：
组合（同 子序列）共 个，每种组合长度平均为 ，即生成一个需要
题目3.返回没有重复值数组的全部排列
测试链接
思路
用交换原数组下标代替 path 的功能，时空占用更低
答案
复杂度 ^2
时间复杂度：（ 相对 可被忽略）
一共 个数，第一个位置有 种可能、第二个位置有 种可能，即：，每种排列长度为 ，即生成一个需要
题目4.返回可能有重复值数组的全部排列，排列要求去重
测试链接
思路
用交换原数组下标代替 path 的功能，时空占用更低
答案
复杂度
同 题目3
题目5.用递归逆序一个栈
答案
package main
import "fmt"
func main() {
stack := []int{1, 2, 3, 4, 5}
reverseStack(&stack)
fmt.Println(stack) // [5 4 3 2 1]
}
// 用递归函数逆序栈
func reverseStack(stack *[]int) {
if len(*stack) == 0 {
return
}
bottom := bottomOut(stack)
reverseStack(stack)
*stack = append(*stack, bottom)
}
// 栈底元素移除掉，上面的元素盖下来
// 返回移除掉的栈底元素
func bottomOut(stack *[]int) int {
n := len(*stack)
top := (*stack)[n-1]
*stack = (*stack)[:n-1]
if n == 1 { // 栈空
return top
} else {
bottom := bottomOut(stack)
*stack = append(*stack, top)
return bottom
}
}图解
bottomOut：移除并返回栈底元素
reverseStack：逆序栈
复杂度
时间复杂度：
bottomOut：；reverseStack：
题目6.用递归排序一个栈
思路
实现 4 个递归方法：
- 返回栈的深度
- 告诉深度，返回该深度栈中的最大值
- 告诉深度和最大值，返回有几个最大值
- 告诉深度、最大值和最大值个数，让最大值都沉底，其他保持顺序不变
答案
package main
import (
"fmt"
"math"
"math/rand"
)
const (
N = 20
V = 100
TEST_TIMES = 20000
)
// 用递归排序栈
// 栈只提供 push、pop、isEmpty 三个方法
func sortStack(stack *[]int) {
depth := getDepth(stack)
for depth > 0 {
val := getMaxVal(stack, depth)
count := getCount(stack, depth, val)
setDown(stack, depth, val, count)
depth -= count
}
}
// 返回栈的深度
func getDepth(stack *[]int) int {
n := len(*stack)
if n == 0 {
return 0
}
top := (*stack)[n-1]
*stack = (*stack)[:n-1]
depth := getDepth(stack) + 1
*stack = append(*stack, top)
return depth
}
// 返回 depth 深的栈的最大值
func getMaxVal(stack *[]int, depth int) int {
if depth == 0 {
return math.MinInt
}
n := len(*stack)
top := (*stack)[n-1]
*stack = (*stack)[:n-1]
maxx := getMaxVal(stack, depth-1)
*stack = append(*stack, top)
return max(top, maxx)
}
// 返回 depth 深的栈, val 的个数
func getCount(stack *[]int, depth int, val int) int {
if depth == 0 {
return 0
}
n := len(*stack)
top := (*stack)[n-1]
*stack = (*stack)[:n-1]
count := getCount(stack, depth-1, val)
*stack = append(*stack, top)
if top == val {
return count + 1
}
return count
}
// depth 深的栈，有 count 个 val
// 将它们压到最底下，其他相对次序不变
func setDown(stack *[]int, depth int, val int, count int) {
if depth == 0 {
for ; count > 0; count-- {
*stack = append(*stack, val)
}
} else {
n := len(*stack)
top := (*stack)[n-1]
*stack = (*stack)[:n-1]
setDown(stack, depth-1, val, count)
if top != val {
*stack = append(*stack, top)
}
}
}
func main() {
for i := 0; i < TEST_TIMES; i++ {
arr := getRandomArr()
n := len(arr)
sortStack(&arr)
if !isSorted(arr, n) {
panic("error")
}
}
fmt.Println("success")
}
func getRandomArr() []int {
n := rand.Intn(N)
arr := make([]int, n)
for i := 0; i < n; i++ {
arr[i] = rand.Intn(V)
}
return arr
}
func isSorted(arr []int, length int) bool {
n := len(arr)
if length != n {
return false
}
for i := 1; i < n; i++ {
if arr[i-1] < arr[i] {
return false
}
}
return true
}复杂度
时间复杂度：
4 个递归方法都是
题目7.打印 n 层汉诺塔问题的最优移动轨迹
思路
忘掉左中右，抽象成 from、to、other
f(i, form, to, other)： 号圆盘在 form，要移到 to 去
三个步骤完成：
- 将 号圆盘从
from移到other，这样 号圆盘上面就没有比它小的圆盘盖着它了 - 将
form处的 号圆盘移到to - 将 号圆盘从
other移到to
答案
package main
import "fmt"
func main() {
hanoi(3)
}
func hanoi(n int) {
if n > 0 {
f(n, "左", "右", "中")
}
}
// 1 - i 号圆盘在 form，要移到 to 去
func f(i int, from, to, other string) {
if i == 1 {
fmt.Printf("将 %d 号圆盘从 %s 移动到 %s\n", i, from, to)
} else {
// 将 1 - i-1 号圆盘从 from 移到 other
// 这样 i 号圆盘上面就没有比它小的圆盘盖着它了
f(i-1, from, other, to)
// 将 form 处的 i 号圆盘移到 to
fmt.Printf("将 %d 号圆盘从 %s 移动到 %s\n", i, from, to)
// 将 1 - i-1 号圆盘从 other 移到 to
f(i-1, other, to, from)
}
}复杂度
时间复杂度：
层汉诺塔问题，最优移动轨迹是 步：
剪枝
剪枝一种可以提高搜索算法时间和空间效率的技巧，经过剪枝和其他优化策略优化过的算法在执行效率上远超一般未经剪枝的算法。甚至有些暴力搜索过不了时限的算法，也可以通过各种剪枝+优化大大缩短算法运行时间，成功通过时效限制
剪枝都有哪几类？
可行性剪枝
如果当前状态和题意不符，并且由于题目可以推出，往后的所有情况和题意都不符，那么就可以进行剪枝，直接把这种情况及后续的所有情况判负，直接返回
排除等效冗余
当几个枝桠具有完全相同的效果的时候，只选择其中一个走就可以了
最优性剪枝
所谓最优性剪枝，是在我们用搜索方法解决最优化问题的时候的一种常用剪枝方法。当搜到一半的时候，发现比已经搜索到的最优解差，则该方案肯定是不行的，即刻停止搜索，进行回溯
顺序剪枝
普遍来讲，搜索的顺序是不固定的，对一个问题来讲，算法可以进入搜索树的任意的一个子节点。但假如我们要搜索一个最小值，而非要从最大值存在的那个节点开搜，就可能存在搜索到最后才出解。而我们从最小的节点开搜很可能马上就出解。这就是顺序剪枝的一个应用。一般来讲，有单调性存在的搜索问题可以和贪心思想结合，进行顺序剪枝
记忆化
记录搜索的每一个状态，当重复搜索到相同的状态的时候直接返回