Leetcode 回溯问题

回溯法是啥

回溯法是一种通过试探性选择与撤销来系统性地搜索问题所有可能解的算法。它特别适合解决组合、排列、子集等需要穷举可能性并筛选有效解的问题。

回溯法有以下两个核心思想：

试错思想：逐步构建候选解，当发现当前路径无法得到有效解时，立即回退到上一步尝试其他
状态管理：通过递归的栈机制保存路径状态，每次选择后进入下一层递归，回溯时撤销当前选择

回溯法有以下三个关键步骤：

选择与撤销：每次选择一个元素加入路径，递归结束后必须撤销该选择，以尝试其他可能性
终止条件：当路径满足解的条件时（如长度等于目标值），保存结果并返回
剪枝优化：提前跳过无效分支（如重复元素、不可能满足约束的路径），减少递归次数

通用回溯模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82


// 通用回溯模板（Go版本）
func solveProblem(nums []int) [][]int {
    // 1. 预处理（排序/初始化）
    sort.Ints(nums) // 去重时需要排序
    res := [][]int{}

    // 2. 定义回溯函数（使用闭包捕获状态）
    var backtrack func(
        path []int,        // 当前路径：已做出的选择序列
        selection []int,   // 选择列表：当前可选的元素集合
        used []bool,       // 辅助参数：标记已使用的元素（根据问题调整）
        start int,         // 辅助参数：组合问题中的起始位置（根据问题调整）
    )

    backtrack = func(path, selection []int, used []bool, start int) {
        // 终止条件（根据具体问题修改）
        if len(path) == len(nums) {
            res = append(res, append([]int{}, path...))
            return
        }
        
        // 横向遍历选择列表（根据问题调整遍历方式）
        for i := 0; i < len(selection); i++ {
            // 剪枝判断（根据问题需要添加条件）
            if used[i] {
                continue // 示例：跳过已使用的元素
            }
            if i > 0 && selection[i] == selection[i-1] && !used[i-1] {
                continue // 示例：横向去重
            }
            
            // 做选择（更新路径和状态）
            newPath := append([]int{}, path...) // 创建新路径
            newPath = append(newPath, selection[i])
            newUsed := append([]bool{}, used...)
            newUsed[i] = true
            
            // 进入下一层决策树（更新选择列表和参数）
            backtrack(
                newPath,   // 更新后的路径
                selection, // 新的选择列表（可能保持不变）
                newUsed,   // 更新后的使用状态
                i+1,       // 新的起始位置（组合问题用）
            )
            
            // Go不需要显式回溯操作，因为使用的是传值而不是引用
            // 每次迭代都使用新的path和used副本
        }
    }

    // 3. 初始调用（根据问题设置初始参数）
    backtrack(
        []int{},   // 初始路径：空路径
        nums,      // 初始选择列表：完整数组
        make([]bool, len(nums)), // 初始辅助参数：未使用的标记数组
        0,         // 初始起始位置：从0开始
    )

    return res
}

/* 参数说明：
1. 初始路径：回溯的起点，通常是空切片 []
   - 排列问题：空路径
   - 组合问题：空路径
   - 子集问题：空路径

2. 初始选择列表：第一层可供选择的元素集合
   - 排列问题：完整数组
   - 组合问题：完整数组（配合start参数使用）
   - 子集问题：完整数组

3. 辅助参数：根据问题需要传递的额外状态
   - used []bool：标记已使用元素（排列问题必需）
   - start int：控制选择范围的起始索引（组合问题必需）
   - sum int：当前路径的累计值（组合总和问题需要）
   - index int：当前处理位置（分割问题需要）

4. 优化思路：如何优化
   - used 有时可改全局变量，这个时候需要显式回溯
   - selection 有些时候是全集就无需传入 
*/

回溯问题刷题

排列问题

题号	题目名称	难度	关键点
46	全排列	中等	基础排列模板
47	全排列 II	中等	含重复元素的去重
996	正方形数组的数目	困难	排列+数学验证
267	回文排列 II	中等	排列+回文特性剪枝

掌握used数组的使用
理解i>0 && nums[i]==nums[i-1] && !used[i-1]的去重逻辑
处理特殊约束条件（如回文排列）

组合问题

题号	题目名称	难度	关键点
39	组合总和	中等	元素可重复使用
40	组合总和 II	中等	含重复元素的去重
216	组合总和 III	中等	固定长度组合
77	组合	中等	基础组合问题

start参数的控制
总和限制的剪枝sum + candidates[i] > target
去重条件 i > start && candidates[i] == candidates[i-1]

子集问题

题号	题目名称	难度	关键点
78	子集	中等	基础子集模板
90	子集 II	中等	含重复元素的去重
491	递增子序列	中等	序列约束+去重
320	列举单词缩写	中等	特殊形式的子集生成

学习重点：收集所有中间路径处理无序子集的去重特殊约束条件的处理（如递增序列）

分割问题

题号	题目名称	难度	关键点
131	分割回文串	中等	基础分割模板
93	复原IP地址	中等	多段限制条件
282	给表达式添加运算符	困难	分割+运算符插入
1593	拆分字符串使唯一子字符串数目最大	中等	分割+哈希去重

学习重点：分割位置的遍历子段合法性的预判断处理复杂约束（如IP地址段限制）

棋盘问题

题号	题目名称	难度	关键点
51	N皇后	困难	经典棋盘问题
37	解数独	困难	双重回溯+剪枝
980	不同路径 III	困难	网格回溯+访问标记
1219	黄金矿工	中等	网格回溯+价值累计

学习重点：二维空间的回溯高效的状态标记与恢复复杂约束条件的处理（如数独规则）

排列问题（Permutation）

特征：元素顺序敏感，每个元素必须使用且仅用一次
变种：含重复元素、部分排列（如n选k）
核心要点：
- 必须使用used数组记录使用状态
- 去重条件：nums[i] == nums[i-1] && !used[i-1]
- 时间复杂度：O(n!)

排列问题模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


func permute(nums []int) [][]int {
    sort.Ints(nums)
    res := [][]int{}
    used := make([]bool, len(nums))

    var dfs func(path []int)
    dfs = func(path []int) {
        if len(path) == len(nums) {
            res = append(res, append([]int{}, path...))
            return
        }
        
        for i := 0; i < len(nums); i++ {
            if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
                continue
            }
            used[i] = true
            dfs(append(path, nums[i]))
            used[i] = false
        }
    }

    dfs([]int{})
    return res
}

LC46. 全排列（无重复）

我觉得这里就是，我选了显式回溯，没有用模板里面的值传递，这样的原因主要是重复利用内存

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


func permute(nums []int) [][]int {

    res := make([][]int, 0)
    used := make([]bool, len(nums))

    var dfs func([]int)
    dfs = func(pick []int){
        // 终止条件
        if len(pick) == len(nums){
            res = append(res, append([]int{}, pick...))
            return 
        }

        // 横向遍历
        for i := 0; i < len(nums); i ++{
            if used[i]{
                continue
            }

            // 显式回溯
            pick = append(pick, nums[i]) 
            used[i] = true 
            dfs(pick)
            used[i] = false 
            pick = pick[:len(path)-1]
        }
    }

    dfs([]int{})
    return res 
}

LC47. 全排列 II（含重复）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


func permuteUnique(nums []int) [][]int {
    sort.Ints(nums)
    res := make([][]int, 0)
    used := make([]bool, len(nums))

    var dfs func([]int)
    dfs = func(pick []int){
        if len(pick) == len(nums){
            res = append(res, append([]int{}, pick...))
            return 
        }
        for i := 0; i < len(nums); i++ {
            if used[i]{
                continue 
            }
            
            // 层级去重
            if i > 0 && nums[i] == nums[i-1] && !used[i-1]{
                continue 
            }

            // 显式处理回溯
            used[i] = true 
            pick = append(pick, nums[i])
            dfs(pick)
            pick = pick[:len(pick)-1]
            used[i] = false
        }
    }

    dfs([]int{})
    return res 
}

LC996. 正方形数组的数目

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


func numSquarefulPerms(nums []int) int {
    sort.Ints(nums)
    res := 0
    used := make([]bool, len(nums))

    var isSquare func(int) bool
    isSquare = func(n int) bool{
        return n == int(math.Sqrt(float64(n))) * int(math.Sqrt(float64(n)))
    }

    var dfs func([]int)
    dfs = func(pick []int){
        if len(pick) == len(nums){
            res ++ 
            return 
        }

        for i := 0 ; i < len(nums); i++ {
            // 基础，不重复使用
            if used[i]{
                continue 
            }
            // 初步，层级去重
            if i > 0 && nums[i] == nums[i-1] && !used[i-1]{
                continue
            }
            // 进阶，相邻数字和是完全平方数
            if len(pick) > 0 && !isSquare(pick[len(pick)-1] + nums[i]){
                continue 
            }
            // 显式回溯
            used[i] = true
            pick = append(pick, nums[i])
            dfs(pick)
            pick = pick[:len(pick)-1] 
            used[i] = false
        }
    }

    dfs([]int{})
    return res
}

组合问题（Combination）

特征：元素顺序不重要，关注元素的选择
变种：元素可重复使用、组合总和限制
核心要点
- 使用start参数避免重复组合
- 剪枝条件：sum + candidates[i] > target
- 时间复杂度：O(2^n)

组合问题模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


func combinationSum(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    res := [][]int{}

    var dfs func(start int, path []int, sum int)
    dfs = func(start int, path []int, sum int) {
        if sum == target {
            res = append(res, append([]int{}, path...))
            return
        }
        
        for i := start; i < len(candidates); i++ {
            // 提前剪枝：如果当前元素已经超过目标值
            if sum + candidates[i] > target {
                break
            }
            // 横向去重：跳过同一层的重复元素
            if i > start && candidates[i] == candidates[i-1] {
                continue
            }
            dfs(i+1, append(path, candidates[i]), sum + candidates[i])
        }
    }

    dfs(0, []int{}, 0)
    return res
}

LC77. 组合（n中选k）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func combine(n int, k int) [][]int {
	
    res := make([][]int, 0)

    var dfs func([]int, int)
    dfs = func(pick []int, idx int){
        // 终止条件
        if len(pick) == k{
            res = append(res, append([]int{}, pick...))
            return 
        }
        // idx 的用处就是往前走不回头
        for i := idx; i <= n; i++{
            dfs(append(pick, i), i+1)
        }
    }

    dfs([]int{}, 1)
    return res
}

LC39. 组合总和（可重复使用）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func combinationSum(nums []int, target int) [][]int {
    
    sort.Ints(nums)
    res := make([][]int, 0)

    var dfs func([]int, int, int)
    dfs = func(pick []int, idx, sum int){
        // 终止条件
        if sum == target{
            res = append(res, append([]int{}, pick...))
            return 
        }else if sum > target{
            return 
        }
        // 横向遍历
        for i := idx; i < len(nums); i++ {
            dfs(append(pick, nums[i]), i, sum+nums[i])
        }
    }

    dfs([]int{}, 0, 0)
    return res
}

LC40. 组合总和 II（不可重复）

这里一个是加上used来横向去重，一个是递归的时候i+1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


func combinationSum2(nums []int, target int) [][]int {
    
    sort.Ints(nums)
    res := make([][]int, 0)
    used := make([]bool, len(nums))

    var dfs func([]int, int, int)
    dfs = func(pick []int, idx, sum int){
        // 终止条件
        if sum == target{
            res = append(res, append([]int{}, pick...))
            return 
        }else if sum > target{
            return 
        }
        // 横向遍历
        for i := idx; i < len(nums); i++{
            if i > 0 && nums[i] == nums[i-1] && !used[i-1]{
                continue
            }
            used[i] = true 
            dfs(append(pick, nums[i]), i+1, sum+nums[i])
            used[i] = false 
        }
    }

    dfs([]int{}, 0, 0)
    return res
}

LC216. 组合总和 III

这里就是不用去重，需要i+1，同时增加剪枝条件

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func combinationSum3(k int, n int) [][]int {
    
    res := make([][]int, 0)

    var dfs func([]int, int, int)
    dfs = func(pick []int, idx, sum int){
        // 满足条件
        if sum == n && len(pick) == k{
            res = append(res, append([]int{}, pick...))
            return 
        }
        // 这里要么是超额完成任务，要么是提前完成任务
        if  sum >= n{
            return  
        }
        // 横向遍历
        for i := idx; i < 10; i ++{
            dfs(append(pick, i), i+1, sum+i)
        }
    }

    dfs([]int{}, 1, 0)
    return res
}

子集问题（Subset）

特征：需要所有可能的子集变种：含重复元素、求特定大小子集核心要点：

收集所有中间路径
去重条件与组合问题类似
时间复杂度：O(n 2^n)

子集问题模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func subsetsWithDup(nums []int) [][]int {
    sort.Ints(nums)
    res := [][]int{}

    var dfs func(start int, path []int)
    dfs = func(start int, path []int) {
        // 每个节点都记录结果
        res = append(res, append([]int{}, path...))
        
        for i := start; i < len(nums); i++ {
            // 跳过同一层的重复元素
            if i > start && nums[i] == nums[i-1] {
                continue
            }
            dfs(i+1, append(path, nums[i]))
        }
    }

    dfs(0, []int{})
    return res
}

78. 子集（无重复）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func subsets(nums []int) [][]int {
    res := make([][]int, 0)

    var dfs func([]int, int)
    dfs = func(pick []int, u int){
        // 终止条件
        if u == len(nums){
            res = append(res, append([]int{}, pick...))
            return 
        }
        // 不用显式回溯
        dfs(pick, u+1)
        dfs(append(pick, nums[u]), u+1)
    }

    dfs([]int{}, 0)
    return res
}

LC90. 子集 II（含重复）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


func subsetsWithDup(nums []int) [][]int {
    // 有重复先排序
    sort.Ints(nums)
    res := make([][]int, 0)
    used := make([]bool, len(nums))

    var dfs func([]int, int)
    dfs = func(pick []int, idx int){
        if idx == len(nums){
            res = append(res, append([]int{}, pick...))
            return 
        }
        // 不选
        dfs(pick, idx+1)
        // 层级去重
        if idx > 0 && nums[idx] == nums[idx-1] && !used[idx-1]{
            return 
        }
        // 选
        used[idx] = true
        dfs(append(pick, nums[idx]), idx+1)
        used[idx] = false
    }

    dfs([]int{}, 0)
    return res
}

LC491. 递增子序列

这题的used非常重要

不可以用全局数组，会影响
要在递归层来统计，而且统计的是数字而不是下标

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


func findSubsequences(nums []int) [][]int {
    res := make([][]int, 0)

    var dfs func([]int, int)
    dfs = func(pick []int, idx int){
        // 每个节点都可能是结果
        if len(pick) > 1{
            res = append(res, append([]int{}, pick...))
        }
        // 核心步骤，记录的是同层的数字而不是坐标
        used := make(map[int]bool)
        for i := idx; i < len(nums); i++{
            // 同层去重，这个很重要
            if used[nums[i]]{
                continue 
            }
            // 保证递增
            if len(pick) == 0 || nums[i] >= pick[len(pick)-1]{
                used[nums[i]] = true
                dfs(append(pick, nums[i]), i+1)
            }
        }
    }

    dfs([]int{}, 0)
    return res 
}

LC320. 列举单词缩写

VIP，没买

分割问题（Partition）

特征：将字符串/数组分割为满足条件的子段变种：回文分割、IP地址复原核心要点：

分割位置作为选择点
先验证子段合法性再递归
时间复杂度：O(n 2^n)

分割问题模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func partition(s string) [][]string {
    res := [][]string{}

    var dfs func(start int, path []string)
    dfs = func(start int, path []string) {
        if start >= len(s) {
            res = append(res, append([]string{}, path...))
            return
        }
        
        for end := start+1; end <= len(s); end++ {
            substr := s[start:end]
            if isPalindrome(substr) {
                dfs(end, append(path, substr))
            }
        }
    }

    dfs(0, []string{})
    return res
}

131. 分割回文串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


func partition(s string) [][]string {
    n := len(s)

    // 记录哪个字符串是回文串
    dp := make([][]bool, n)
    for i := 0; i < n; i++{
        dp[i] = make([]bool, n)
        dp[i][i] = true 
    }

    // 动规计算
    for i := 1; i < n; i++{
        for j := 0; j+i < n; j++{
            if i == 1 {
                dp[j][j+i] = (s[j] == s[j+i])
            } else {
                dp[j][j+i] = dp[j+1][j+i-1] && (s[j] == s[j+i])
            }
        }
    } 

    // DFS
    res := make([][]string, 0)
    var dfs func([]string, int)
    dfs = func(pick []string, idx int){
        // 终止条件
        if idx == len(s){
            res = append(res, append([]string{}, pick...))
            return 
        }
        // 横向遍历
        for i := idx; i < n; i++{
            if dp[idx][i]{
                dfs(append(pick, s[idx:i+1]), i+1)
            }
        }
    }

    dfs([]string{}, 0)
    return res
}

LC93. 复原IP地址

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


func restoreIpAddresses(s string) []string {
    if len(s) < 4 || len(s) > 12 {
        return []string{}
    }

    res := make([]string, 0)
    var dfs func(string, int, int)
    dfs = func(ip string, idx, cnt int){
        // 终止条件
        if cnt == 4 && idx == len(s){
            res = append(res, ip[:len(ip)-1])
            return 
        }else if cnt == 4 || idx == len(s){
            return 
        }else if s[idx] == '0'{
            dfs(ip+"0.", idx+1, cnt+1)
            return 
        }
        // 横向遍历
        sum := 0
        for i := idx; i < len(s); i++{
            sum = 10*sum + int(s[i]-'0')
            if sum > 255{
                break
            }
            dfs(ip+strconv.Itoa(sum)+".", i+1, cnt+1)
        }
    }

    dfs("", 0, 0)
    return res
}

LC1593. 拆分字符串使唯一子字符串数目最大

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


func maxUniqueSplit(s string) int {
    res := 0	

    var dfs func(map[string]bool, int, int)
    dfs = func(m map[string]bool, idx, cnt int){
        // 终止条件
        if idx == len(s){
            res = max(res, cnt)
            return 
        }else if cnt + len(s) - idx < res{
            return 
        }
        // 横向遍历
        for i := idx; i < len(s); i++{
            word := s[idx:i+1]
            if !m[word]{
                m[word] = true
                dfs(m, i+1, cnt+1)
                m[word] = false
            }
        }
    }
    dfs(make(map[string]bool), 0, 0)
    return res
}

棋盘问题（Chessboard）

特征：二维空间的约束满足变种：N皇后、数独、路径搜索核心要点：

二维遍历与约束检查
高效的状态标记与恢复
时间复杂度：通常为指数级

LC51. N皇后

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


func solveNQueens(n int) [][]string {
	
	res := make([][]string, 0)
	base := ""
	for i := 0; i < n; i ++{
		base += "."
	}

	var dfs func([]string, int, int, int, int)
	dfs = func(path []string, row, col, pie, na int){
		if row == n{
			res = append(res, append([]string{}, path...))
			return 
		}

		bits := ^(col | pie | na) & ((1 << n) - 1)
		for bits > 0{
			pick := bits & (-bits)
			pos := 0
			for i := pick; i > 1; i = i >> 1{
				pos++
			}
			newRow := base[:pos] + "Q" + base[pos+1:]
			dfs(append(path, newRow), row+1, col|pick, (pie|pick)<<1, (na|pick)>>1)
			bits = bits & (bits-1)
		}
	}

	dfs(make([]string, 0), 0, 0, 0, 0)
	return res
}