如果你问搞算法的人什么解法最没技术含量十有八九会得到同一个答案暴力求解。四个循环套在一起硬跑既不优雅也不高效看起来就像新手交作业。但我做了这些年算法相关的开发得替暴力法说句公道话它被低估得太严重了。这篇文章我会把 C 里暴力求解的几种核心形态——枚举、回溯、DFS、BFS、剪枝——从头到尾拆一遍相关的代码模板、复杂度计算、隐藏的坑我都会提到。不管你是刚入门的初学者还是想把算法体系梳理清楚的老手看完应该都能对暴力法有一个全新的认识。1. 暴力法被低估的三个场景它比你想的更能打1.1 小数据范围里暴力就是最优解很多人一看到题目就默认要写高级算法实际上很多题目的数据范围根本不需要花哨解法。比如 n ≤ 20 的排列组合、n ≤ 100 的两两配对直接写暴力可能比写动态规划更快更稳而且不会因为状态转移方程写错而调试到怀疑人生。我说个小范围的典型感受我自己处理过不少接口联调时的模拟数据需求比如从几十个候选里枚举所有组合去生成测试用例这时候没有任何算法比三层循环更直接。代码短、逻辑透明、一眼能看出对不对这本身就是生产环境里极大的优点。复杂算法可以带来性能但也带来理解和维护成本在小数据场景里这笔交易往往不划算。1.2 对拍验证暴力是复杂算法的裁判暴力法的第二个价值说出来很多人会觉得意外——它是验证复杂算法正确性的裁判。所谓对拍就是拿一个绝对正确但可能很慢的暴力实现去验证一个高效但容易写错的优化实现。只要小规模随机数据下两个程序输出一致优化版本的正确性就有了底气。我写线段树、树状数组这类数据结构时十次里有八次会先写一个暴力版当基准。优化版跑得快但边界条件多、容易出细节错暴力版虽然慢但逻辑简单几乎不可能写错。两者对着跑随机数据一旦结果不一致我几乎总能从暴力版的输出里反推出是优化版的哪一步出了问题。这个习惯帮我省下了无数调试时间。1.3 暴力是推导正解的起点第三暴力法还是推导正确解法的起点。你回头看很多教科书算法本质上都是暴力 剪枝 用数据结构加速的产物。二分答案是枚举答案的优化动态规划是在记录已经搜索过的状态ST 表是把区间查询的暴力预处理换成了倍增思想。所以我不太认同暴力是没办法才用的退路这种说法。先把暴力写出来你才能真正看清楚哪些计算是重复的、哪些搜索是无效的然后才知道该往哪个方向优化。跳过暴力直接想正解就像没打草稿直接写作文容易飘。2. 枚举的三种正统写法循环、位掩码与 next_permutation枚举是暴力法的第一板斧。所谓枚举就是把所有可能的情况不重不漏地列一遍逐个判断是否满足条件。C 里最常用的枚举手段就三种我一个个说。2.1 循环枚举最朴素也最直接的表达循环枚举最好理解就是 for 嵌套 for。经典的两数之和题目要求在一个数组里找到两个下标使它们对应的数字之和等于 target。最直观的写法就是两层循环外层固定第一个数内层从它后面找第二个数#include vector using namespace std; vectorint twoSum(vectorint nums, int target) { int n nums.size(); for (int i 0; i n; i) { for (int j i 1; j n; j) { if (nums[i] nums[j] target) { return {i, j}; } } } return {}; }这段代码的逻辑一句话就能说清i 确定第一个数j 从 i1 开始避免重复配对找到就返回。时间复杂度 O(n²)空间 O(1)。这里有个容易忽略的细节为什么 j 要从 i1 开始而不是从 0 开始因为 (i, j) 和 (j, i) 是同一种配对从 i1 开始可以直接砍掉一半的枚举量。这是枚举不重不漏原则的典型体现——如果没有这个约束你还得额外开一个标记数组去重白白增加复杂度和出错概率。循环枚举的适用场景很明确解空间是规则的、多维的比如二维坐标、区间组合、矩阵遍历。实际写代码时我见到更多的问题反而是循环边界写错比如该写 n写成了 n或者j i 1写成了j 0这种低级失误造成的死循环和越界比算法设计错误更常见。2.2 子集枚举位掩码的妙用第二个高频场景是枚举一个集合的所有子集。比如给定数组 [1, 2, 3]要输出所有子集用循环硬写会很痛苦因为你不知道要嵌套几层循环。这时候位掩码bitmask就派上用场了。原理一句话用一个 n 位的二进制数表示子集第 i 位是 1 就表示包含第 i 个元素是 0 就不包含。所以从 0 到(1 n) - 1的所有整数恰好对应全部 2ⁿ 个子集#include iostream #include vector using namespace std; vectorvectorint subsets(vectorint nums) { int n nums.size(); vectorvectorint result; for (int mask 0; mask (1 n); mask) { vectorint sub; for (int i 0; i n; i) { if (mask (1 i)) { sub.push_back(nums[i]); } } result.push_back(sub); } return result; }外层循环每取一个 mask内层循环逐位检查哪些元素该入选。这里有两个重点一是(1 n)在 n 超过 30 时要小心因为按 int 计算会溢出成负数。实际做题时子集枚举基本只用在社会 n ≤ 20 的场景2²⁰ 1,048,576 还勉强能跑到 n 25 的 3 千多万次循环就已经很吃力了。二是mask (1 i)这个判断要理解成检查第 i 位是否为 1别跟逻辑与混在一起。位掩码还有一个隐藏好处它天然支持状态记录。你以后学状态压缩动态规划就会发现dp[mask]里的 mask 就是从这来的。暴力枚举子集是理解状态压缩的第一步。2.3 全排列next_permutation 的正确打开方式枚举一个序列的全部排列是最容易写错的一类枚举。自己写递归当然可以但 C 标准库其实给了现成的函数——next_permutation它能把当前序列原地改成字典序的下一个排列改不动了返回 false。用起来是这么个套路#include algorithm #include vector using namespace std; vectorvectorint permute(vectorint nums) { sort(nums.begin(), nums.end()); vectorvectorint result; do { result.push_back(nums); } while (next_permutation(nums.begin(), nums.end())); return result; }这里有一个几乎每个人都会踩的坑调用 next_permutation 之前必须先排序。因为这个函数从当前序列出发找的是字典序更大的下一个如果初始序列不是最小的字典序排列你得到的排列集合就不完整。先 sort 一下保证从最小的排列开始才能不漏。全排列的复杂度是 O(n!)所以 n 超过 11 或 12 就非常吃力了。4! 248! 4032010! 3628800如果你对 n 10 的每个排列做 O(n) 级别的处理也就是几千万次操作勉强能过n 12 的 4.79 亿次就基本完蛋了。用之前一定先算算账。3. 回溯与DFS把试错写成代码的核心套路如果说枚举是把所有情况列出来回溯就是一条路走到黑走不通了再回头。很多算法题——排列组合、N 皇后、数独、括号生成——本质都是回溯。它和枚举最大的区别在于枚举把候选情况全部生成一遍回溯则是在生成过程中不断剪掉已经知道没希望的分支。3.1 回溯的框架其实就三板斧我习惯把回溯题拆成三个动作选择、递归、撤销。给你一个通用骨架void backtrack(当前状态, 可选列表) { if (满足结束条件) { 记录答案; return; } for (每个可选项) { 做出选择; backtrack(更新后的状态, 更新后的可选列表); 撤销选择; // 关键 } }这个骨架看着简单但撤销选择这一步是无数人容易漏掉的。为什么必须撤销因为回溯是在同一个状态空间里反复尝试如果不把上一个选择的痕迹擦掉下一个分支就会带着旧状态往下走结果自然是错的。这也是回溯和 DFS 最核心的区别记忆点DFS 重在遍历回溯重在尝试后再回头。我用最经典的 N 皇后举例。要在 n × n 的棋盘上放 n 个皇后使得任意两个皇后不在同一行、同一列、同一对角线上。按行搜索每行放一个用 col 数组记录每行皇后所在的列用三个布尔数组记录哪些列、哪些对角线已经被占用#include iostream #include vector using namespace std; int n, total 0; vectorint col; vectorbool usedCol, usedDiag1, usedDiag2; void dfs(int row) { if (row n) { total; return; } for (int c 0; c n; c) { int d1 row c; // 主对角线编号 int d2 row - c n - 1; // 副对角线编号 if (usedCol[c] || usedDiag1[d1] || usedDiag2[d2]) { continue; } col[row] c; usedCol[c] usedDiag1[d1] usedDiag2[d2] true; dfs(row 1); usedCol[c] usedDiag1[d1] usedDiag2[d2] false; } }对角线编号这里可能有人看不懂。在主对角线上任意两个格子的行号减列号相等即row - c是常数在副对角线上行号加列号是常数。为了防止row - c出现负数统一加上 n - 1 平移到非负区间。这个映射技巧在很多棋盘类问题里都能复用值得记下来。3.2 回溯的三个高频坑第一状态忘记还原。我见过有人只用 col 数组记录但不恢复 usedCol导致第一行选过的列后面永远不能用。判断回溯写没写对最简单的自检方法就是递归函数里做选择和撤销选择的代码必须严格对称。如果做了选择却没有对称撤销迟早出问题。第二把可变容器以引用方式传入后压入答案时没做拷贝。比如往全局 result 里result.push_back(path)如果 path 后续还会被修改那存进去的其实就是同一块内存里不断变化的内容最后拿到的可能全是空列表或同一个状态。正确做法是存拷贝——直接用值传参或者显式result.push_back(vectorint(path))。第三剪枝顺序不讲究。有些分支明明在第一层就能判断没戏却写到了递归最深处才判断白白多走很多路。剪枝要尽量前移判断条件能放在 for 循环入口就直接放别等到下一层递归里才 continue。这个习惯对数据稍大的回溯题往往就是能跑和跑不动的分水岭。4. BFS与状态空间搜索暴力里最讲章法的一类回溯解决的问题是求所有可行解但问题变成求从状态 A 到状态 B 的最少步数时就该轮到 BFS 上场了。很多人不把 BFS 当暴力但它的本质确实是暴力——把状态空间一层一层全部铺开逐层检查。差别在于BFS 讲究层的概念因此天然能算最短步数。4.1 先想清楚状态是什么写 BFS 之前我建议你先问自己一个问题这个问题的一个状态到底由哪些变量组成比如走迷宫状态就是 (x, y) 坐标比如倒水问题状态就是两个桶当前的水量比如八数码状态就是整个棋盘的排列。把状态定义清楚了搜索才能开始。这里最容易被忽略的是状态数会不会爆炸。如果状态空间是无限的或者呈指数级增长BFS 是跑不完的。所以实际工程里BFS 通常要配合一个 visited 数组保证每个状态只入队一次。一旦允许重复入队队列长度会失去控制内存和时间一起崩。4.2 最短步数的套路可以直接抄我直接给一个网格迷宫的 BFS 模板0 表示空地1 表示墙求从起点到终点的最短路径长度#include iostream #include vector #include queue using namespace std; int shortestPath(vectorvectorint grid, int sx, int sy, int tx, int ty) { int n grid.size(), m grid[0].size(); int dx[] {1, -1, 0, 0}; int dy[] {0, 0, 1, -1}; vectorvectorint dist(n, vectorint(m, -1)); queuepairint, int q; q.push({sx, sy}); dist[sx][sy] 0; while (!q.empty()) { auto [x, y] q.front(); q.pop(); if (x tx y ty) { return dist[x][y]; } for (int k 0; k 4; k) { int nx x dx[k], ny y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (grid[nx][ny] 1) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } return -1; // 到不了终点 }这套代码有几个值得留意的点。dist 数组初值设为 -1 有两个作用一是标记未访问二是记录从起点到该点的最短距离一步到位省了单独开 visited。判断越界、撞墙、已访问的顺序尽量固定别想着合并条件保持三条 continue 清晰可读排查问题的时候非常省事。BFS 的复杂度也好算每个状态访问一次每次扩展的边数是常数总共 O(状态数 × 扩展边数)。对网格题来说就是 O(n × m)非常可观。这就是为什么说 BFS 是暴力但高效——它不靠聪明剪枝靠的是第一次访问到终点时路径一定最短这条层次遍历的天然性质。4.3 BFS 去重的一个进阶细节状态如果只是一个坐标用二维数组去重就够了。但很多问题的状态是组合型的比如有三个人要同时移动状态就得是 (x1, y1, x2, y2, x3, y3) 的六元组。这时候要么压缩成一维索引要么用哈希表存字符串。我自己的习惯是能压缩就压缩因为哈希表慢而且占内存。坐标范围不大时完全可以把每个坐标编码成x * m y再把多个坐标拼成一个整数或一个 long long性能和可读性都能兼顾。压缩编码这个思路不只是 BFS 能用凡是遇到多维状态去重的场景都可以套用。我见过很多人在状态压缩这一步偷懒结果爆内存其实多写两行就能解决。5. 剪枝让暴力解法从超时边缘到稳稳通过说实话纯暴力很多时候确实过不了大数据。但暴力系解法的魅力在于加几行剪枝往往就能把指数级的搜索空间砍到可以接受的范围。剪枝不是独立的算法它是暴力法的灵魂配件。5.1 剪枝的本质是提前宣告失败想象你在一棵树上找果实如果不剪枝你得爬遍整棵树的每个枝杈。剪枝就是你走到某个枝杈的起点看一眼就发现这上面不可能有目标果实于是直接绕道。对应到代码里就是在递归或循环的某个早期位置加上一个判断不满足就直接 return 或 continue。判断的原则很简单这个判断必须安全——就是说被剪掉的分支里确实不可能存在合法答案。如果剪错了你会漏解这种 bug 比超时更可怕因为它不一定能通过随机测试发现。所以每次加剪枝之前我都会在心里把这个分支为什么一定无解的理由说清楚说不清就不加。5.2 我常用的四种剪枝手法第一是可行性剪枝。当前路径已经违反约束比如 N 皇后里某列已被占用直接跳过。这是回溯天然自带的剪枝也是最好写的一种。第二是最优性剪枝。搜索目标是找最优解比如求最短路径、最小花费当当前已消耗的成本已经大于等于目前找到的最优值时这个分支可以直接砍掉。用这个手法定性上很有效但提醒一句得先有一个全局的当前最优值变量初始值要设到足够大比如int best 0x3f3f3f3f否则第一次比较就会出问题。第三是排序优化。搜索顺序对回溯效率影响巨大。比如组合求和问题里先把数组从小到大排序一旦当前数已经大于剩余目标值后面更大的数都无需尝试一个 break 就能截断整片分支。这类剪枝性价比极高因为排序本身是 O(n log n)却能换来指数级的搜索量下降。第四是重复状态的缓存也叫记忆化。把已经算过的某种状态的答案记下来下次遇到相同状态直接取。严格来说这是动态规划的雏形但在暴力搜索里提前用上记忆化是让会超时的暴力变成能通过的搜索的最快路径。如果你发现一个暴力搜索函数反复用同样的参数调用别犹豫开个数组或哈希表存答案。5.3 一个完整的剪枝示例看一个组合总和问题给定一个无重复元素的候选数组和一个目标值找出所有可使数字和等于目标值的组合每个数字可以重复使用。先排序搜索过程里如果当前候选数已经大于剩余 target直接 break这就是我上面说的排序 可行性剪枝的组合#include iostream #include vector #include algorithm using namespace std; vectorvectorint result; vectorint path; void dfs(vectorint candidates, int target, int start) { if (target 0) { result.push_back(path); return; } for (int i start; i candidates.size(); i) { if (candidates[i] target) break; // 剪枝核心 path.push_back(candidates[i]); dfs(candidates, target - candidates[i], i); path.pop_back(); } } vectorvectorint combinationSum(vectorint candidates, int target) { sort(candidates.begin(), candidates.end()); dfs(candidates, target, 0); return result; }注意这里 dfs 的第三个参数是 i不是 i 1。原因很简单每个数字可以重复使用所以选了 candidates[i] 之后下一层还可以继续从 i 开始选如果题目改成每个数字只能用一次才需要改成 i 1。这个细节我在不少人的代码里见过错误小数据能跑出结果数据稍大就错得很隐蔽。这个题如果不剪枝n 个候选数、target 又比较大的时候搜索树会非常庞大。加了排序加大于就 break 之后大部分无效分支在很浅的层就被截断了实测小数据下速度差距能到几十倍。从这个例子你可以看到剪枝本身并不神秘它就是提前判断、快速放弃八个字。6. 我踩过的暴力法相关的坑今天一起说了写了不少年代码暴力法相关的坑我踩得算是比较全的挑几个值得说的分享出来希望能帮你绕开。6.1 四个隐藏很深的低级错误第一个坑是数据类型溢出。暴力法的枚举量一大累加和、乘积、下标计算很容易溢出 int。比如子集枚举里(1 n)n 到 31 就成负数了比如求阶乘做全排列预处理13! 就已经超过 int 范围。我现在的习惯是凡是和数量级沾边的变量一律用 long long最多多占几个字节但能省掉一整类玄学 bug。判断溢出有个土办法就是看结果是不是突然变成负数或者数值明显不对。第二个坑是 next_permutation 忘了先排序。这个我在好几个初学者的代码里反复看到。函数本身的语义是求字典序下一个排列不是列出所有排列。你初始序列是乱序它只会从当前排列往后枚举一部分前面的排列全丢了。记住全排列三连是先 sort、再 do-while、最后 next_permutation。第三个坑是位运算优先级。mask (1 i) 0这种写法实际会被解析成mask ((1 i) 0)因为 的优先级高于 。正确的习惯是给位运算加括号(mask (1 i)) 0。这个坑特别隐蔽因为编译能过、结果也经常碰巧对——只有某些位恰好是 0 的时候才出错随机测试不一定能测出来。第四个坑是回溯里的引用污染。如果你把 path 以引用传给递归函数又在里面继续 push_back 和 pop_back代码本身没问题但一旦你在某个分支里把 path 存进了结果容器后面改动就会污染之前存的答案。最稳妥的方法是存储时显式拷贝或者干脆值传递。6.2 暴力程序的调试三板斧暴力程序出错我一般先缩小数据范围把 n 改成 5 以内手工推一遍答案再用打印把每一步的选择过程打出来对比。回溯类问题我会在递归入口打印当前行、当前列、当前状态看它是不是走了不该走的分支。这个操作看着笨但比对着代码干瞪眼快得多。还有一个我特别喜欢的小技巧暴力版和优化版用同样的随机数据对拍跑几百组输出不一致的地方就是突破口。暴力版逻辑简单不容易写错拿它当参照物能精准定位优化版是哪一步引入了错误。这个思路在面试和竞赛里都很好用算是暴力法的隐藏价值之一。6.3 从暴力到正解的进阶路线最后给还在学习的朋友一个建议。暴力法不是终点但它是你手里最可靠的兜底工具。我建议你先用暴力把枚举、回溯、DFS、BFS 这几类题型吃透能独立写出框架、能讲清楚每一步在做什么然后再去学二分、双指针、动态规划、图论算法。你会发现很多所谓的高级算法其实就是暴力加上了一个聪明的剪枝或加速结构。先把笨办法练熟了聪明办法才能学得扎实。真到面试或者比赛中遇到没见过的题能写出一个正确的暴力解也永远比什么都写不出来强——先拿到分再谈优化这是最实在的经验。
