Java数据结构与算法之枚举与模拟

枚举与模拟

学习目标

• 理解枚举算法的基本思想
• 掌握枚举的优化技巧
• 理解模拟算法的应用场景
• 能够使用枚举和模拟解决实际问题
• 掌握剪枝优化的方法
• 能够分析枚举算法的时间复杂度

知识结构思维导图

#mermaid-svg-K8ZK5BKtAieChQ1V{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-K8ZK5BKtAieChQ1V .error-icon{fill:#552222;}#mermaid-svg-K8ZK5BKtAieChQ1V .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-K8ZK5BKtAieChQ1V .marker{fill:#333333;stroke:#333333;}#mermaid-svg-K8ZK5BKtAieChQ1V .marker.cross{stroke:#333333;}#mermaid-svg-K8ZK5BKtAieChQ1V svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-K8ZK5BKtAieChQ1V p{margin:0;}#mermaid-svg-K8ZK5BKtAieChQ1V .edge{stroke-width:3;}#mermaid-svg-K8ZK5BKtAieChQ1V .section–1 rect,#mermaid-svg-K8ZK5BKtAieChQ1V .section–1 path,#mermaid-svg-K8ZK5BKtAieChQ1V .section–1 circle,#mermaid-svg-K8ZK5BKtAieChQ1V .section–1 polygon,#mermaid-svg-K8ZK5BKtAieChQ1V .section–1 path{fill:hsl(240, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .section–1 text{fill:#ffffff;}#mermaid-svg-K8ZK5BKtAieChQ1V .node-icon–1{font-size:40px;color:#ffffff;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-edge–1{stroke:hsl(240, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-depth–1{stroke-width:17;}#mermaid-svg-K8ZK5BKtAieChQ1V .section–1 line{stroke:hsl(60, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled circle,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:lightgray;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:#efefef;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-0 rect,#mermaid-svg-K8ZK5BKtAieChQ1V .section-0 path,#mermaid-svg-K8ZK5BKtAieChQ1V .section-0 circle,#mermaid-svg-K8ZK5BKtAieChQ1V .section-0 polygon,#mermaid-svg-K8ZK5BKtAieChQ1V .section-0 path{fill:hsl(60, 100%, 73.5294117647%);}#mermaid-svg-K8ZK5BKtAieChQ1V .section-0 text{fill:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .node-icon-0{font-size:40px;color:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-edge-0{stroke:hsl(60, 100%, 73.5294117647%);}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-depth-0{stroke-width:14;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-0 line{stroke:hsl(240, 100%, 83.5294117647%);stroke-width:3;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled circle,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:lightgray;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:#efefef;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-1 rect,#mermaid-svg-K8ZK5BKtAieChQ1V .section-1 path,#mermaid-svg-K8ZK5BKtAieChQ1V .section-1 circle,#mermaid-svg-K8ZK5BKtAieChQ1V .section-1 polygon,#mermaid-svg-K8ZK5BKtAieChQ1V .section-1 path{fill:hsl(80, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .section-1 text{fill:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .node-icon-1{font-size:40px;color:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-edge-1{stroke:hsl(80, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-depth-1{stroke-width:11;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-1 line{stroke:hsl(260, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled circle,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:lightgray;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:#efefef;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-2 rect,#mermaid-svg-K8ZK5BKtAieChQ1V .section-2 path,#mermaid-svg-K8ZK5BKtAieChQ1V .section-2 circle,#mermaid-svg-K8ZK5BKtAieChQ1V .section-2 polygon,#mermaid-svg-K8ZK5BKtAieChQ1V .section-2 path{fill:hsl(270, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .section-2 text{fill:#ffffff;}#mermaid-svg-K8ZK5BKtAieChQ1V .node-icon-2{font-size:40px;color:#ffffff;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-edge-2{stroke:hsl(270, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-depth-2{stroke-width:8;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-2 line{stroke:hsl(90, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled circle,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:lightgray;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:#efefef;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-3 rect,#mermaid-svg-K8ZK5BKtAieChQ1V .section-3 path,#mermaid-svg-K8ZK5BKtAieChQ1V .section-3 circle,#mermaid-svg-K8ZK5BKtAieChQ1V .section-3 polygon,#mermaid-svg-K8ZK5BKtAieChQ1V .section-3 path{fill:hsl(300, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .section-3 text{fill:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .node-icon-3{font-size:40px;color:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-edge-3{stroke:hsl(300, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-depth-3{stroke-width:5;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-3 line{stroke:hsl(120, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled circle,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:lightgray;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:#efefef;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-4 rect,#mermaid-svg-K8ZK5BKtAieChQ1V .section-4 path,#mermaid-svg-K8ZK5BKtAieChQ1V .section-4 circle,#mermaid-svg-K8ZK5BKtAieChQ1V .section-4 polygon,#mermaid-svg-K8ZK5BKtAieChQ1V .section-4 path{fill:hsl(330, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .section-4 text{fill:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .node-icon-4{font-size:40px;color:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-edge-4{stroke:hsl(330, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-depth-4{stroke-width:2;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-4 line{stroke:hsl(150, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled circle,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:lightgray;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:#efefef;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-5 rect,#mermaid-svg-K8ZK5BKtAieChQ1V .section-5 path,#mermaid-svg-K8ZK5BKtAieChQ1V .section-5 circle,#mermaid-svg-K8ZK5BKtAieChQ1V .section-5 polygon,#mermaid-svg-K8ZK5BKtAieChQ1V .section-5 path{fill:hsl(0, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .section-5 text{fill:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .node-icon-5{font-size:40px;color:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-edge-5{stroke:hsl(0, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-depth-5{stroke-width:-1;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-5 line{stroke:hsl(180, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled circle,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:lightgray;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:#efefef;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-6 rect,#mermaid-svg-K8ZK5BKtAieChQ1V .section-6 path,#mermaid-svg-K8ZK5BKtAieChQ1V .section-6 circle,#mermaid-svg-K8ZK5BKtAieChQ1V .section-6 polygon,#mermaid-svg-K8ZK5BKtAieChQ1V .section-6 path{fill:hsl(30, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .section-6 text{fill:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .node-icon-6{font-size:40px;color:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-edge-6{stroke:hsl(30, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-depth-6{stroke-width:-4;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-6 line{stroke:hsl(210, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled circle,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:lightgray;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:#efefef;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-7 rect,#mermaid-svg-K8ZK5BKtAieChQ1V .section-7 path,#mermaid-svg-K8ZK5BKtAieChQ1V .section-7 circle,#mermaid-svg-K8ZK5BKtAieChQ1V .section-7 polygon,#mermaid-svg-K8ZK5BKtAieChQ1V .section-7 path{fill:hsl(90, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .section-7 text{fill:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .node-icon-7{font-size:40px;color:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-edge-7{stroke:hsl(90, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-depth-7{stroke-width:-7;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-7 line{stroke:hsl(270, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled circle,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:lightgray;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:#efefef;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-8 rect,#mermaid-svg-K8ZK5BKtAieChQ1V .section-8 path,#mermaid-svg-K8ZK5BKtAieChQ1V .section-8 circle,#mermaid-svg-K8ZK5BKtAieChQ1V .section-8 polygon,#mermaid-svg-K8ZK5BKtAieChQ1V .section-8 path{fill:hsl(150, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .section-8 text{fill:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .node-icon-8{font-size:40px;color:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-edge-8{stroke:hsl(150, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-depth-8{stroke-width:-10;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-8 line{stroke:hsl(330, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled circle,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:lightgray;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:#efefef;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-9 rect,#mermaid-svg-K8ZK5BKtAieChQ1V .section-9 path,#mermaid-svg-K8ZK5BKtAieChQ1V .section-9 circle,#mermaid-svg-K8ZK5BKtAieChQ1V .section-9 polygon,#mermaid-svg-K8ZK5BKtAieChQ1V .section-9 path{fill:hsl(180, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .section-9 text{fill:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .node-icon-9{font-size:40px;color:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-edge-9{stroke:hsl(180, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-depth-9{stroke-width:-13;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-9 line{stroke:hsl(0, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled circle,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:lightgray;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:#efefef;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-10 rect,#mermaid-svg-K8ZK5BKtAieChQ1V .section-10 path,#mermaid-svg-K8ZK5BKtAieChQ1V .section-10 circle,#mermaid-svg-K8ZK5BKtAieChQ1V .section-10 polygon,#mermaid-svg-K8ZK5BKtAieChQ1V .section-10 path{fill:hsl(210, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .section-10 text{fill:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .node-icon-10{font-size:40px;color:black;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-edge-10{stroke:hsl(210, 100%, 76.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .edge-depth-10{stroke-width:-16;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-10 line{stroke:hsl(30, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled circle,#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:lightgray;}#mermaid-svg-K8ZK5BKtAieChQ1V .disabled text{fill:#efefef;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-root rect,#mermaid-svg-K8ZK5BKtAieChQ1V .section-root path,#mermaid-svg-K8ZK5BKtAieChQ1V .section-root circle,#mermaid-svg-K8ZK5BKtAieChQ1V .section-root polygon{fill:hsl(240, 100%, 46.2745098039%);}#mermaid-svg-K8ZK5BKtAieChQ1V .section-root text{fill:#ffffff;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-root span{color:#ffffff;}#mermaid-svg-K8ZK5BKtAieChQ1V .section-2 span{color:#ffffff;}#mermaid-svg-K8ZK5BKtAieChQ1V .icon-container{height:100%;display:flex;justify-content:center;align-items:center;}#mermaid-svg-K8ZK5BKtAieChQ1V .edge{fill:none;}#mermaid-svg-K8ZK5BKtAieChQ1V .mindmap-node-label{dy:1em;alignment-baseline:middle;text-anchor:middle;dominant-baseline:middle;text-align:center;}#mermaid-svg-K8ZK5BKtAieChQ1V :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

枚举与模拟

枚举算法

基本概念

穷举所有可能

暴力搜索

完全遍历

枚举类型

线性枚举

排列枚举

组合枚举

子集枚举

优化技巧

剪枝

去重

提前终止

空间优化

模拟算法

基本概念

按题意模拟

过程模拟

状态模拟

应用场景

日期计算

进制转换

游戏模拟

过程模拟

实现技巧

状态管理

边界处理

特殊情况

复杂度分析

时间复杂度

指数级

阶乘级

多项式级

空间复杂度

递归深度

状态存储

一、枚举算法

1.1 枚举的基本概念

枚举（Enumeration）：
也称为穷举法，列举所有可能的情况，逐一检验是否满足条件

核心思想：
– 列举所有可能的解
– 检验每个解是否满足条件
– 找出所有满足条件的解

特点：
– 思路简单，容易实现
– 保证能找到所有解
– 时间复杂度通常较高
– 适合数据规模较小的问题

适用场景：
– 数据规模小（n ≤ 20）
– 没有更优算法
– 需要找出所有解
– 作为其他算法的基础

1.2 为什么需要枚举？

场景1：找出所有满足条件的组合

问题：从1到n中选出k个数，使它们的和等于target

暴力枚举：
– 列举所有k个数的组合
– 检查每个组合的和是否等于target
– 时间复杂度：O(C(n,k))

场景2：验证算法正确性

问题：实现了一个复杂算法，如何验证正确性？

方法：
– 用枚举算法生成小规模测试数据的正确答案
– 对比复杂算法的输出
– 验证算法的正确性

场景3：没有更优解法

问题：某些NP完全问题

特点：
– 没有已知的多项式时间算法
– 枚举可能是唯一可行的方法
– 需要配合剪枝优化

二、线性枚举

2.1 基本线性枚举

/**
* 线性枚举示例：找出数组中所有和为target的两个数
*/
public class LinearEnumeration {
/**
* 枚举所有两数组合
*/
public List<int[]> findPairs(int[] nums, int target) {
List<int[]> result = new ArrayList<>();
int n = nums.length;

// 枚举第一个数
for (int i = 0; i < n; i++) {
// 枚举第二个数
for (int j = i + 1; j < n; j++) {
// 检查是否满足条件
if (nums[i] + nums[j] == target) {
result.add(new int[]{i, j});
}
}
}

return result;
}

/**
* 三数之和
*/
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;

// 排序，便于去重
Arrays.sort(nums);

// 枚举第一个数
for (int i = 0; i < n – 2; i++) {
// 去重
if (i > 0 && nums[i] == nums[i – 1]) {
continue;
}

// 枚举第二个数
for (int j = i + 1; j < n – 1; j++) {
// 去重
if (j > i + 1 && nums[j] == nums[j – 1]) {
continue;
}

// 枚举第三个数
for (int k = j + 1; k < n; k++) {
// 去重
if (k > j + 1 && nums[k] == nums[k – 1]) {
continue;
}

if (nums[i] + nums[j] + nums[k] == 0) {
result.add(Arrays.asList(nums[i], nums[j], nums[k]));
}
}
}
}

return result;
}
}

2.2 枚举优化：双指针

/**
* 三数之和优化版本
*/
public List<List<Integer>> threeSumOptimized(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;

Arrays.sort(nums);

for (int i = 0; i < n – 2; i++) {
if (i > 0 && nums[i] == nums[i – 1]) {
continue;
}

// 使用双指针代替两层循环
int left = i + 1;
int right = n – 1;
int target = –nums[i];

while (left < right) {
int sum = nums[left] + nums[right];

if (sum == target) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));

// 去重
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right – 1]) {
right—;
}

left++;
right—;
} else if (sum < target) {
left++;
} else {
right—;
}
}
}

return result;
}

三、排列枚举

3.1 全排列

/**
* 全排列
*/
public class Permutation {
/**
* 生成数组的全排列
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] used = new boolean[nums.length];

backtrack(nums, path, used, result);
return result;
}

private void backtrack(int[] nums,
List<Integer> path,
boolean[] used,
List<List<Integer>> result) {
// 找到一个完整排列
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}

// 枚举下一个位置可以选择的数
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue; // 已经使用过
}

// 选择
path.add(nums[i]);
used[i] = true;

// 递归
backtrack(nums, path, used, result);

// 撤销选择（回溯）
path.remove(path.size() – 1);
used[i] = false;
}
}

/**
* 全排列II（包含重复元素）
*/
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] used = new boolean[nums.length];

// 排序，便于去重
Arrays.sort(nums);

backtrackUnique(nums, path, used, result);
return result;
}

private void backtrackUnique(int[] nums,
List<Integer> path,
boolean[] used,
List<List<Integer>> result) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}

for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}

// 去重：如果当前元素与前一个元素相同，且前一个元素未使用
// 说明前一个元素已经在同一层被使用过了
if (i > 0 && nums[i] == nums[i – 1] && !used[i – 1]) {
continue;
}

path.add(nums[i]);
used[i] = true;

backtrackUnique(nums, path, used, result);

path.remove(path.size() – 1);
used[i] = false;
}
}
}

执行过程示例：

输入：[1, 2, 3]

枚举过程：
[]
/ | \\
[1] [2] [3]
/ \\ / \\ / \\
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]

结果：
[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

3.2 下一个排列

/**
* 下一个排列
*/
public class NextPermutation {
/**
* 找到下一个字典序更大的排列
*/
public void nextPermutation(int[] nums) {
int n = nums.length;

// 1. 从右向左找到第一个升序对(i, i+1)
int i = n – 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i—;
}

if (i >= 0) {
// 2. 从右向左找到第一个大于nums[i]的数
int j = n – 1;
while (j >= 0 && nums[j] <= nums[i]) {
j—;
}

// 3. 交换nums[i]和nums[j]
swap(nums, i, j);
}

// 4. 反转i+1到末尾的部分
reverse(nums, i + 1, n – 1);
}

private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}

private void reverse(int[] nums, int start, int end) {
while (start < end) {
swap(nums, start, end);
start++;
end—;
}
}
}

四、组合枚举

4.1 组合

/**
* 组合
*/
public class Combination {
/**
* 从n个数中选k个数的所有组合
*/
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();

backtrack(n, k, 1, path, result);
return result;
}

private void backtrack(int n,
int k,
int start,
List<Integer> path,
List<List<Integer>> result) {
// 找到一个完整组合
if (path.size() == k) {
result.add(new ArrayList<>(path));
return;
}

// 剪枝：如果剩余数字不够，直接返回
// 还需要选择的数字个数：k – path.size()
// 剩余可选的数字个数：n – start + 1
if (n – start + 1 < k – path.size()) {
return;
}

// 枚举下一个可以选择的数
for (int i = start; i <= n; i++) {
path.add(i);
backtrack(n, k, i + 1, path, result);
path.remove(path.size() – 1);
}
}

/**
* 组合总和
*/
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();

Arrays.sort(candidates); // 排序，便于剪枝
backtrackSum(candidates, target, 0, path, result);
return result;
}

private void backtrackSum(int[] candidates,
int target,
int start,
List<Integer> path,
List<List<Integer>> result) {
if (target == 0) {
result.add(new ArrayList<>(path));
return;
}

for (int i = start; i < candidates.length; i++) {
// 剪枝：如果当前数已经大于target，后面的数更大，直接返回
if (candidates[i] > target) {
break;
}

path.add(candidates[i]);
// 可以重复使用，所以下一层从i开始
backtrackSum(candidates, target – candidates[i], i, path, result);
path.remove(path.size() – 1);
}
}
}

4.2 子集枚举

/**
* 子集
*/
public class Subset {
/**
* 生成所有子集
*/
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();

backtrack(nums, 0, path, result);
return result;
}

private void backtrack(int[] nums,
int start,
List<Integer> path,
List<List<Integer>> result) {
// 每个状态都是一个子集
result.add(new ArrayList<>(path));

for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
backtrack(nums, i + 1, path, result);
path.remove(path.size() – 1);
}
}

/**
* 使用位运算枚举子集
*/
public List<List<Integer>> subsetsBit(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;

// 枚举所有可能的状态：2^n种
for (int mask = 0; mask < (1 << n); mask++) {
List<Integer> subset = new ArrayList<>();

// 检查每一位
for (int i = 0; i < n; i++) {
// 如果第i位为1，选择nums[i]
if ((mask & (1 << i)) != 0) {
subset.add(nums[i]);
}
}

result.add(subset);
}

return result;
}
}

位运算枚举示例：

输入：[1, 2, 3]

二进制枚举：
000 → []
001 → [1]
010 → [2]
011 → [1, 2]
100 → [3]
101 → [1, 3]
110 → [2, 3]
111 → [1, 2, 3]

结果：
[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

五、模拟算法

5.1 模拟的基本概念

模拟（Simulation）：
按照题目描述的过程，用代码实现整个流程

核心思想：
– 理解题意
– 按步骤实现
– 注意边界条件
– 处理特殊情况

特点：
– 思路直观
– 代码量可能较大
– 需要仔细处理细节
– 容易出错

适用场景：
– 题目明确给出过程
– 没有明显的算法模式
– 需要精确模拟某个过程

5.2 日期计算

/**
* 日期计算
*/
public class DateCalculation {
/**
* 判断是否为闰年
*/
public boolean isLeapYear(int year) {
return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

/**
* 获取某月的天数
*/
public int getDaysInMonth(int year, int month) {
int[] days = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

if (month == 2 && isLeapYear(year)) {
return 29;
}

return days[month];
}

/**
* 计算某一天是星期几（蔡勒公式）
*/
public int getDayOfWeek(int year, int month, int day) {
if (month < 3) {
month += 12;
year—;
}

int c = year / 100;
int y = year % 100;

int w = (y + y / 4 + c / 4 – 2 * c + 26 * (month + 1) / 10 + day – 1) % 7;

// 转换为1-7（周一到周日）
return (w + 7) % 7;
}

/**
* 计算两个日期之间的天数
*/
public int daysBetween(int year1, int month1, int day1,
int year2, int month2, int day2) {
int days = 0;

// 计算从year1-month1-day1到year1年底的天数
days += getDaysInMonth(year1, month1) – day1;
for (int m = month1 + 1; m <= 12; m++) {
days += getDaysInMonth(year1, m);
}

// 计算中间完整年份的天数
for (int y = year1 + 1; y < year2; y++) {
days += isLeapYear(y) ? 366 : 365;
}

// 计算从year2年初到year2-month2-day2的天数
for (int m = 1; m < month2; m++) {
days += getDaysInMonth(year2, m);
}
days += day2;

return days;
}

/**
* 计算n天后的日期
*/
public int[] addDays(int year, int month, int day, int n) {
while (n > 0) {
int daysInMonth = getDaysInMonth(year, month);
int remainingDays = daysInMonth – day;

if (n <= remainingDays) {
day += n;
break;
}

n -= (remainingDays + 1);
day = 1;
month++;

if (month > 12) {
month = 1;
year++;
}
}

return new int[]{year, month, day};
}
}

5.3 进制转换

/**
* 进制转换
*/
public class BaseConversion {
/**
* 十进制转任意进制
*/
public String decimalToBase(int num, int base) {
if (num == 0) {
return "0";
}

StringBuilder result = new StringBuilder();
boolean negative = num < 0;
num = Math.abs(num);

while (num > 0) {
int digit = num % base;

// 处理大于9的数字（用A-Z表示）
if (digit < 10) {
result.append((char)('0' + digit));
} else {
result.append((char)('A' + digit – 10));
}

num /= base;
}

if (negative) {
result.append('-');
}

return result.reverse().toString();
}

/**
* 任意进制转十进制
*/
public int baseToDecimal(String num, int base) {
int result = 0;
boolean negative = num.charAt(0) == '-';
int start = negative ? 1 : 0;

for (int i = start; i < num.length(); i++) {
char c = num.charAt(i);
int digit;

if (c >= '0' && c <= '9') {
digit = c – '0';
} else {
digit = c – 'A' + 10;
}

result = result * base + digit;
}

return negative ? –result : result;
}

/**
* 二进制加法
*/
public String addBinary(String a, String b) {
StringBuilder result = new StringBuilder();
int i = a.length() – 1;
int j = b.length() – 1;
int carry = 0;

while (i >= 0 || j >= 0 || carry > 0) {
int sum = carry;

if (i >= 0) {
sum += a.charAt(i) – '0';
i—;
}

if (j >= 0) {
sum += b.charAt(j) – '0';
j—;
}

result.append(sum % 2);
carry = sum / 2;
}

return result.reverse().toString();
}
}

5.4 矩阵模拟

/**
* 矩阵模拟
*/
public class MatrixSimulation {
/**
* 螺旋矩阵
*/
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
if (matrix == null || matrix.length == 0) {
return result;
}

int rows = matrix.length;
int cols = matrix[0].length;
int top = 0, bottom = rows – 1;
int left = 0, right = cols – 1;

while (top <= bottom && left <= right) {
// 从左到右
for (int j = left; j <= right; j++) {
result.add(matrix[top][j]);
}
top++;

// 从上到下
for (int i = top; i <= bottom; i++) {
result.add(matrix[i][right]);
}
right—;

// 从右到左
if (top <= bottom) {
for (int j = right; j >= left; j—) {
result.add(matrix[bottom][j]);
}
bottom—;
}

// 从下到上
if (left <= right) {
for (int i = bottom; i >= top; i—) {
result.add(matrix[i][left]);
}
left++;
}
}

return result;
}

/**
* 旋转矩阵
*/
public void rotate(int[][] matrix) {
int n = matrix.length;

// 先转置
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}

// 再水平翻转
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n – 1 – j];
matrix[i][n – 1 – j] = temp;
}
}
}

/**
* 生成螺旋矩阵
*/
public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
int num = 1;
int top = 0, bottom = n – 1;
int left = 0, right = n – 1;

while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) {
matrix[top][j] = num++;
}
top++;

for (int i = top; i <= bottom; i++) {
matrix[i][right] = num++;
}
right—;

for (int j = right; j >= left; j—) {
matrix[bottom][j] = num++;
}
bottom—;

for (int i = bottom; i >= top; i—) {
matrix[i][left] = num++;
}
left++;
}

return matrix;
}
}

5.5 游戏模拟

/**
* 生命游戏
*/
public class GameOfLife {
/**
* 生命游戏规则：
* 1. 活细胞周围有2-3个活细胞，继续存活
* 2. 死细胞周围有3个活细胞，变为活细胞
* 3. 其他情况，细胞死亡
*/
public void gameOfLife(int[][] board) {
int rows = board.length;
int cols = board[0].length;

// 8个方向
int[][] directions = {
{–1, –1}, {–1, 0}, {–1, 1},
{0, –1}, {0, 1},
{1, –1}, {1, 0}, {1, 1}
};

// 第一次遍历：标记状态变化
// 0: 死 → 死
// 1: 活 → 活
// 2: 活 → 死
// 3: 死 → 活
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int liveNeighbors = 0;

// 统计周围活细胞数量
for (int[] dir : directions) {
int ni = i + dir[0];
int nj = j + dir[1];

if (ni >= 0 && ni < rows && nj >= 0 && nj < cols) {
// 1和2都表示原来是活细胞
if (board[ni][nj] == 1 || board[ni][nj] == 2) {
liveNeighbors++;
}
}
}

// 应用规则
if (board[i][j] == 1) {
// 活细胞
if (liveNeighbors < 2 || liveNeighbors > 3) {
board[i][j] = 2; // 活 → 死
}
} else {
// 死细胞
if (liveNeighbors == 3) {
board[i][j] = 3; // 死 → 活
}
}
}
}

// 第二次遍历：更新状态
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == 2) {
board[i][j] = 0;
} else if (board[i][j] == 3) {
board[i][j] = 1;
}
}
}
}
}

六、枚举优化技巧

6.1 剪枝

/**
* N皇后问题
*/
public class NQueens {
/**
* N皇后问题：在N×N的棋盘上放置N个皇后，使它们互不攻击
*/
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
char[][] board = new char[n][n];

// 初始化棋盘
for (int i = 0; i < n; i++) {
Arrays.fill(board[i], '.');
}

backtrack(board, 0, result);
return result;
}

private void backtrack(char[][] board, int row, List<List<String>> result) {
if (row == board.length) {
result.add(construct(board));
return;
}

// 枚举当前行的每一列
for (int col = 0; col < board.length; col++) {
// 剪枝：检查是否可以放置
if (!isValid(board, row, col)) {
continue;
}

// 放置皇后
board[row][col] = 'Q';

// 递归下一行
backtrack(board, row + 1, result);

// 回溯
board[row][col] = '.';
}
}

/**
* 检查是否可以在(row, col)放置皇后
*/
private boolean isValid(char[][] board, int row, int col) {
int n = board.length;

// 检查列
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') {
return false;
}
}

// 检查左上对角线
for (int i = row – 1, j = col – 1; i >= 0 && j >= 0; i—, j—) {
if (board[i][j] == 'Q') {
return false;
}
}

// 检查右上对角线
for (int i = row – 1, j = col + 1; i >= 0 && j < n; i—, j++) {
if (board[i][j] == 'Q') {
return false;
}
}

return true;
}

private List<String> construct(char[][] board) {
List<String> result = new ArrayList<>();
for (char[] row : board) {
result.add(new String(row));
}
return result;
}
}

6.2 去重

/**
* 去重技巧
*/
public class Deduplication {
/**
* 组合总和II（包含重复元素，但每个元素只能使用一次）
*/
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();

// 排序，便于去重
Arrays.sort(candidates);

backtrack(candidates, target, 0, path, result);
return result;
}

private void backtrack(int[] candidates,
int target,
int start,
List<Integer> path,
List<List<Integer>> result) {
if (target == 0) {
result.add(new ArrayList<>(path));
return;
}

for (int i = start; i < candidates.length; i++) {
// 去重：跳过同一层的重复元素
if (i > start && candidates[i] == candidates[i – 1]) {
continue;
}

// 剪枝
if (candidates[i] > target) {
break;
}

path.add(candidates[i]);
backtrack(candidates, target – candidates[i], i + 1, path, result);
path.remove(path.size() – 1);
}
}
}

6.3 提前终止

/**
* 提前终止优化
*/
public class EarlyTermination {
/**
* 找到第一个满足条件的解就返回
*/
public boolean exist(char[][] board, String word) {
int rows = board.length;
int cols = board[0].length;
boolean[][] visited = new boolean[rows][cols];

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (dfs(board, word, 0, i, j, visited)) {
return true; // 找到一个解就返回
}
}
}

return false;
}

private boolean dfs(char[][] board,
String word,
int index,
int i,
int j,
boolean[][] visited) {
if (index == word.length()) {
return true; // 找到完整单词
}

int rows = board.length;
int cols = board[0].length;

if (i < 0 || i >= rows || j < 0 || j >= cols ||
visited[i][j] || board[i][j] != word.charAt(index)) {
return false;
}

visited[i][j] = true;

// 尝试四个方向
boolean found = dfs(board, word, index + 1, i – 1, j, visited) ||
dfs(board, word, index + 1, i + 1, j, visited) ||
dfs(board, word, index + 1, i, j – 1, visited) ||
dfs(board, word, index + 1, i, j + 1, visited);

visited[i][j] = false;

return found;
}
}

七、复杂度分析

7.1 时间复杂度

枚举算法的时间复杂度：

1. 线性枚举：
– 一层循环：O(n)
– 两层循环：O(n²)
– k层循环：O(n^k)

2. 排列枚举：
– 全排列：O(n!)
– 部分排列：O(n!/(n-k)!)

3. 组合枚举：
– 所有组合：O(2^n)
– k个数的组合：O(C(n,k))

4. 子集枚举：
– 所有子集：O(2^n)

常见复杂度对比：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2^n) < O(n!)

数据规模参考：
– n ≤ 10：O(n!)
– n ≤ 20：O(2^n)
– n ≤ 100：O(n³)
– n ≤ 1000：O(n²)
– n ≤ 10^6：O(n log n)
– n ≤ 10^8：O(n)

7.2 空间复杂度

枚举算法的空间复杂度：

1. 递归深度：
– 排列/组合：O(n)
– 子集：O(n)

2. 状态存储：
– visited数组：O(n)
– 路径数组：O(n)
– 结果集合：O(结果数量)

优化技巧：
– 使用位运算代替数组
– 原地修改代替额外空间
– 迭代代替递归

八、经典问题

8.1 数独求解器

/**
* 数独求解器
*/
public class SudokuSolver {
public void solveSudoku(char[][] board) {
solve(board);
}

private boolean solve(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
continue;
}

// 枚举1-9
for (char c = '1'; c <= '9'; c++) {
if (isValid(board, i, j, c)) {
board[i][j] = c;

if (solve(board)) {
return true;
}

board[i][j] = '.';
}
}

return false; // 无解
}
}

return true; // 找到解
}

private boolean isValid(char[][] board, int row, int col, char c) {
for (int i = 0; i < 9; i++) {
// 检查行
if (board[row][i] == c) return false;

// 检查列
if (board[i][col] == c) return false;

// 检查3×3宫格
int boxRow = (row / 3) * 3 + i / 3;
int boxCol = (col / 3) * 3 + i % 3;
if (board[boxRow][boxCol] == c) return false;
}

return true;
}
}

8.2 括号生成

/**
* 括号生成
*/
public class GenerateParentheses {
/**
* 生成所有有效的n对括号组合
*/
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
backtrack(result, new StringBuilder(), 0, 0, n);
return result;
}

private void backtrack(List<String> result,
StringBuilder path,
int open,
int close,
int n) {
if (path.length() == 2 * n) {
result.add(path.toString());
return;
}

// 可以添加左括号
if (open < n) {
path.append('(');
backtrack(result, path, open + 1, close, n);
path.deleteCharAt(path.length() – 1);
}

// 可以添加右括号
if (close < open) {
path.append(')');
backtrack(result, path, open, close + 1, n);
path.deleteCharAt(path.length() – 1);
}
}
}

8.3 电话号码的字母组合

/**
* 电话号码的字母组合
*/
public class LetterCombinations {
private static final String[] MAPPING = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz" // 9
};

public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return result;
}

backtrack(digits, 0, new StringBuilder(), result);
return result;
}

private void backtrack(String digits,
int index,
StringBuilder path,
List<String> result) {
if (index == digits.length()) {
result.add(path.toString());
return;
}

int digit = digits.charAt(index) – '0';
String letters = MAPPING[digit];

for (char c : letters.toCharArray()) {
path.append(c);
backtrack(digits, index + 1, path, result);
path.deleteCharAt(path.length() – 1);
}
}
}

九、算法模板总结

9.1 枚举模板

// ========== 排列模板 ==========
void permute(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> result) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}

for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;

path.add(nums[i]);
used[i] = true;

permute(nums, path, used, result);

path.remove(path.size() – 1);
used[i] = false;
}
}

// ========== 组合模板 ==========
void combine(int n, int k, int start, List<Integer> path, List<List<Integer>> result) {
if (path.size() == k) {
result.add(new ArrayList<>(path));
return;
}

for (int i = start; i <= n; i++) {
path.add(i);
combine(n, k, i + 1, path, result);
path.remove(path.size() – 1);
}
}

// ========== 子集模板 ==========
void subsets(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
result.add(new ArrayList<>(path));

for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
subsets(nums, i + 1, path, result);
path.remove(path.size() – 1);
}
}

// ========== 位运算枚举子集模板 ==========
void subsetsbit(int[] nums) {
int n = nums.length;
for (int mask = 0; mask < (1 << n); mask++) {
List<Integer> subset = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
subset.add(nums[i]);
}
}
// 处理subset
}
}

9.2 回溯模板

// ========== 回溯框架 ==========
void backtrack(状态, 选择列表) {
if (满足结束条件) {
result.add(路径);
return;
}

for (选择 in 选择列表) {
// 剪枝
if (不满足条件) continue;

// 做选择
路径.add(选择);

// 递归
backtrack(新状态, 新选择列表);

// 撤销选择
路径.remove(选择);
}
}

十、练习题精选

10.1 基础练习（10题）

10.2 进阶练习（10题）

十一、学习检查清单

完成本章学习后，你应该能够：

• 理解枚举算法的基本思想
• 掌握线性枚举的实现
• 能够生成全排列
• 能够生成组合
• 能够生成子集
• 理解回溯算法的框架
• 掌握剪枝优化技巧
• 掌握去重技巧
• 理解模拟算法的应用
• 能够实现日期计算
• 能够实现进制转换
• 能够实现矩阵模拟
• 能够分析枚举算法的复杂度
• 掌握枚举和模拟的常用模板
• 能够解决N皇后等经典问题

十二、学习建议

十三、常见错误与陷阱

13.1 忘记回溯

// ✗ 错误：忘记撤销选择
void backtrack(List<Integer> path) {
if (满足条件) {
result.add(path); // 错误：直接添加引用
return;
}

for (int i = 0; i < n; i++) {
path.add(i);
backtrack(path);
// 忘记path.remove(path.size() – 1);
}
}

// ✓ 正确：记得回溯
void backtrack(List<Integer> path) {
if (满足条件) {
result.add(new ArrayList<>(path)); // 创建副本
return;
}

for (int i = 0; i < n; i++) {
path.add(i);
backtrack(path);
path.remove(path.size() – 1); // 回溯
}
}

13.2 去重错误

// ✗ 错误：去重条件错误
if (i > 0 && nums[i] == nums[i – 1]) {
continue; // 会跳过所有重复元素
}

// ✓ 正确：只跳过同一层的重复元素
if (i > start && nums[i] == nums[i – 1]) {
continue;
}

13.3 边界处理错误

// ✗ 错误：没有检查边界
int result = matrix[i][j]; // 可能越界

// ✓ 正确：检查边界
if (i >= 0 && i < rows && j >= 0 && j < cols) {
int result = matrix[i][j];
}

十四、参考资源

在线练习平台：

• LeetCode：https://leetcode.cn/
• 洛谷：https://www.luogu.com.cn/
• 牛客网：https://www.nowcoder.com/

推荐阅读：

• 《算法竞赛进阶指南》：枚举章节
• 《挑战程序设计竞赛》：暴力搜索章节

视频教程：

• B站搜索"回溯算法"
• 慕课网算法课程

下一章预告： 递归与分治

在下一章中，我们将学习递归和分治算法，这是解决复杂问题的重要思想。