文章目录一、回溯算法核心原理1.1 什么是回溯算法1.2 回溯算法的三要素1.3 回溯的树模型1.4 C 语言回溯算法通用框架重中之重二、经典例题实战C 语言完整实现2.1 入门例题全排列问题LeetCode 46. 全排列2.2 基础例题组合问题LeetCode 77. 组合2.3 进阶例题子集问题LeetCode 78. 子集2.4 高阶例题N 皇后问题LeetCode 51. N 皇后三、回溯算法的剪枝优化核心3.1 4 种常见的剪枝场景3.2 剪枝的注意事项四、回溯算法方法论总结4.1 回溯算法通用解题 6 步法4.2 回溯算法的适用场景4.3 常见坑点与避坑指南一、回溯算法核心原理1.1 什么是回溯算法回溯算法是一种基于递归的「试错 - 回退」算法核心逻辑可以类比为走迷宫当你走到死胡同时不会继续往前而是退回到上一个岔路口选择另一条未走过的路继续尝试直到找到出口或遍历完所有路径。1.2 回溯算法的三要素所有回溯问题都可以拆解为三个不可缺少的核心要素这是解题的关键路径Path已经做出的选择也就是当前递归深度下已经选好的元素集合比如全排列中已经选好的数字选择列表Choice List当前步骤中可以做出的选择也就是还能选哪些元素终止条件End Condition到达决策树底层无法再进行选择的条件此时需要收集结果并返回1.3 回溯的树模型我们可以把所有回溯问题抽象成一棵N 叉树树的每一层对应一次选择操作每个节点对应当前的状态路径 可选列表每个分支对应一个具体的选择叶子节点对应满足终止条件的一个有效解举个例子数组[1,2,3]的全排列对应的决策树就是一棵 3 层的 N 叉树第一层可选 1/2/3第二层选剩余的 2 个元素第三层选最后 1 个元素叶子节点就是所有的全排列结果。1.4 C 语言回溯算法通用框架重中之重这是所有回溯题的通用模板99% 的回溯问题都可以通过修改这个框架实现。// 全局变量说明也可通过函数参数传递初学者推荐全局变量减少参数复杂度// result: 存储最终结果的二维/三维数组// path: 存储当前路径的一维数组// 辅助变量: 标记数组used、路径长度pathLen、结果数量resultCount、题目输入参数(n/k/数组等)// 回溯核心函数voidbacktrack(参数列表){// 1. 终止条件到达决策树底层收集结果并返回if(终止条件){将当前路径path存入结果集result;return;}// 2. 遍历选择列表循环处理当前层的所有可选元素for(inti起始位置;i选择列表长度;i){// 可选剪枝操作提前排除不符合条件的分支减少无效递归if(不满足合法条件){continue;}// 3. 处理当前节点做出选择将元素加入路径路径添加操作;标记元素已使用;// 4. 递归进入下一层决策树backtrack(更新后的参数);// 5. 回溯撤销回到上一层撤销刚才的选择和处理节点成对出现路径撤销操作;取消元素标记;}}// 主函数入口intmain(){// 初始化变量、数组、标记位// 调用回溯函数传入初始参数backtrack(初始参数);// 输出最终结果return0;}核心口诀先终止再循环处理递归加回溯。重点强调处理节点和回溯撤销必须成对出现这是回溯算法的灵魂。二、经典例题实战C 语言完整实现本节从易到难精选 4 道回溯算法的经典例题全部基于上述通用框架实现。2.1 入门例题全排列问题LeetCode 46. 全排列思路拆解:路径已经选好的数字组成的当前排列选择列表数组中未被使用的数字用used数组标记是否被使用终止条件路径长度等于数组长度说明已选完所有数字得到一个有效全排列核心点用used数组标记元素使用状态避免重复选择同一个元素代码实现// 全局变量存储结果集、当前路径、结果集大小、当前路径长度、元素使用标记int**res;int*path;intres_size;intpath_size;intused[21];// 因nums元素范围[-10,10]10偏移到[0,20]// 回溯函数生成全排列voidbacktracking(int*nums,intnumsSize,int**returnColumnSizes){// 终止条件当前路径长度等于数组长度找到一个排列if(path_sizenumsSize){// 复制当前路径到临时数组int*tmpmalloc(sizeof(int)*numsSize);for(inti0;inumsSize;i){tmp[i]path[i];}res[res_size]tmp;// 加入结果集(*returnColumnSizes)[res_size]numsSize;// 记录当前排列长度return;}// 遍历每个元素尝试加入路径for(inti0;inumsSize;i){if(used[nums[i]10]1)continue;// 元素已使用跳过used[nums[i]10]1;// 标记已使用path[path_size]nums[i];// 加入当前路径backtracking(nums,numsSize,returnColumnSizes);// 递归used[nums[i]10]0;// 回溯取消使用标记path_size--;// 回溯移除路径最后一个元素}}// 主函数初始化并启动全排列int**permute(int*nums,intnumsSize,int*returnSize,int**returnColumnSizes){res_size0;path_size0;resmalloc(sizeof(int*)*1000);// 分配结果集内存最多1000个排列pathmalloc(sizeof(int)*6);// 分配路径内存numsSize最大6*returnColumnSizesmalloc(sizeof(int)*1000);// 分配每个排列长度的数组backtracking(nums,numsSize,returnColumnSizes);// 启动回溯*returnSizeres_size;// 设置结果集大小returnres;}2.2 基础例题组合问题LeetCode 77. 组合思路拆解组合与排列的核心区别排列讲究顺序[1,2]和[2,1]是两个结果组合不讲究顺序[1,2]和[2,1]是同一个结果路径已经选好的数字集合选择列表当前起始位置之后的数字用startIndex控制避免重复组合终止条件路径长度等于 k得到一个有效组合核心点用startIndex控制每一层的起始选择位置比如第一层选了 1第二层只能从 2 开始选彻底避免重复组合剪枝优化当剩余可选元素数量不足时直接终止循环减少无效枚举代码实现// 全局变量存储结果集、当前路径、当前路径长度、结果集大小int**result;int*path;intpath_size;intresult_size;// 回溯函数生成1~n中选k个数的组合voidbacktracking(intn,intk,intstartIndex){// 终止条件当前路径长度等于k找到一个组合if(path_sizek){// 复制当前路径到临时数组int*tmp(int*)malloc(sizeof(int)*k);for(inti0;ik;i){tmp[i]path[i];}result[result_size]tmp;// 加入结果集return;}// 从startIndex开始遍历避免重复组合for(intistartIndex;in;i){path[path_size]i;// 选当前数加入路径backtracking(n,k,i1);// 递归下一个数从i1开始选path_size--;// 回溯移除路径最后一个数}}// 主函数初始化并启动组合生成int**combine(intn,intk,int*returnSize,int**returnColumnSizes){path(int*)malloc(sizeof(int)*k);// 分配路径内存path_size0;result_size0;result(int**)malloc(sizeof(int*)*184756);// 分配结果集内存C(20,10)最大值backtracking(n,k,1);// 启动回溯从1开始选数*returnSizeresult_size;// 设置结果集大小*returnColumnSizesmalloc(sizeof(int)*result_size);// 分配每个组合长度的数组for(inti0;i*returnSize;i){(*returnColumnSizes)[i]k;// 每个组合长度都是k}returnresult;}2.3 进阶例题子集问题LeetCode 78. 子集思路拆解:子集与组合的核心区别组合只收集决策树叶子节点的结果而子集需要收集决策树所有节点的结果包括根节点的空集路径当前的子集选择列表startIndex之后的元素终止条件startIndex超过数组长度时循环自然结束无需额外终止核心点进入回溯函数后先收集当前路径的结果再进行循环递归确保所有节点都被收录代码实现// 全局变量存储结果集、当前路径、结果集大小、当前路径长度int**res;int*path;intres_size;intpath_size;// 回溯函数生成所有子集voidbacktracking(int*nums,intnumsSize,int**returnColumnSizes,intstartindex){// 先将当前路径加入结果集子集包含空集和所有中间状态int*tmpmalloc(sizeof(int)*path_size);for(inti0;ipath_size;i){tmp[i]path[i];}res[res_size]tmp;(*returnColumnSizes)[res_size]path_size;// 终止条件起始索引越界直接返回if(startindexnumsSize){return;}// 从startindex开始遍历避免重复子集for(intistartindex;inumsSize;i){path[path_size]nums[i];// 选当前元素加入路径backtracking(nums,numsSize,returnColumnSizes,i1);// 递归下一个从i1开始path_size--;// 回溯移除路径最后一个元素}}// 主函数初始化并启动子集生成int**subsets(int*nums,intnumsSize,int*returnSize,int**returnColumnSizes){pathmalloc(sizeof(int)*numsSize);// 分配路径内存resmalloc(sizeof(int*)*1024);// 分配结果集内存最多2^101024个子集path_size0;res_size0;*returnColumnSizesmalloc(sizeof(int)*1024);// 分配每个子集长度的数组backtracking(nums,numsSize,returnColumnSizes,0);// 启动回溯从索引0开始*returnSizeres_size;// 设置结果集大小returnres;}2.4 高阶例题N 皇后问题LeetCode 51. N 皇后思路拆解:路径当前棋盘已放置的皇后位置用一维数组chess[row] col表示第 row 行的皇后放在第 col 列选择列表当前行中满足合法性的列同列、两条对角线无皇后终止条件遍历完所有行row n说明已放完 n 个皇后得到一个有效解核心点按行递归每一行只放一个皇后天然避免同行冲突合法性判断检查同列、45 度对角线、135 度对角线是否有皇后提前剪枝不合法的位置直接跳过不进入递归代码实现// 全局变量存储结果集、当前棋盘、结果集大小、当前处理的行char***res;char**path;intres_size;intdepth;// 判断在(x,y)位置放皇后是否合法intistrue(intn,char**path,intx,inty){// 检查同列是否有皇后for(inti0;ix;i){if(path[i][y]Q)return0;}// 检查左上对角线是否有皇后for(intix-1,jy-1;i0j0;i--,j--){if(path[i][j]Q)return0;}// 检查右上对角线是否有皇后for(intix-1,jy1;i0jn;i--,j){if(path[i][j]Q)return0;}return1;}// 回溯函数按行放置皇后voidbacktracking(intn,intdepth,int**returnColumnSizes){// 终止条件处理完所有行找到一个合法解if(depthn){// 复制当前棋盘到临时数组char**tmpmalloc(sizeof(char*)*n);for(inti0;in;i){tmp[i]malloc(n1);strcpy(tmp[i],path[i]);}res[res_size]tmp;(*returnColumnSizes)[res_size]n;return;}// 遍历当前行的每一列尝试放置皇后for(inti0;in;i){if(istrue(n,path,depth,i)){path[depth][i]Q;// 放置皇后backtracking(n,depth1,returnColumnSizes);// 递归处理下一行path[depth][i].;// 回溯移除皇后}}}// 主函数初始化并启动N皇后求解char***solveNQueens(intn,int*returnSize,int**returnColumnSizes){resmalloc(sizeof(char**)*1000);// 分配结果集内存*returnColumnSizesmalloc(sizeof(int)*1000);pathmalloc(sizeof(char*)*n);// 分配当前棋盘内存// 初始化棋盘为全.for(inti0;in;i){path[i]malloc(n1);memset(path[i],.,n);path[i][n]\0;}res_size0;depth0;backtracking(n,depth,returnColumnSizes);// 启动回溯*returnSizeres_size;returnres;}三、回溯算法的剪枝优化核心回溯的本质是穷举而剪枝是提升回溯效率的唯一核心手段它的核心思想是提前排除不可能得到正确解的分支避免无效的递归和循环。3.1 4 种常见的剪枝场景范围剪枝如组合问题中当剩余可选元素数量不足时直接终止循环减少循环次数合法性剪枝如 N 皇后问题中提前判断位置是否合法不合法直接跳过不进入递归去重剪枝当数组有重复元素时先排序再跳过同一层中重复的元素避免生成重复结果如全排列 II、子集 II约束剪枝如组合总和问题中当当前路径的和已经超过目标值时直接跳过不进入递归3.2 剪枝的注意事项剪枝不能改变最终的结果集只能减少无效枚举剪枝逻辑要放在循环开头或处理节点之后、递归之前提前拦截无效分支。去重剪枝必须先对数组排序否则无法判断相邻重复元素。四、回溯算法方法论总结4.1 回溯算法通用解题 6 步法所有回溯问题都可以按照这 6 个步骤拆解百试百灵确定问题类型判断是排列 / 组合 / 子集 / 棋盘 / 切割类问题确认是否适用回溯拆解三要素明确路径、选择列表、终止条件确定递归参数根据三要素确定回溯函数的入参如 startIndex、used 数组、输入数组等编写终止条件满足条件时收集结果返回上一层编写遍历循环遍历选择列表处理当前节点添加剪枝逻辑递归 回溯处理节点后递归进入下一层递归返回后撤销处理完成回溯4.2 回溯算法的适用场景回溯算法专门解决多层循环无法实现、有明确选择与回退逻辑的枚举问题常见场景如下问题类型典型例题核心特点排列问题全排列、全排列 II讲究顺序用 used 数组标记无 startIndex组合问题组合、组合总和不讲究顺序用 startIndex 控制起始位置子集问题子集、子集 II收集所有节点结果进入函数先收集路径切割问题分割回文串把切割位置当作选择startIndex 控制切割起点棋盘问题N 皇后、解数独二维网格选择核心是合法性判断 剪枝子集和问题目标和、组合总和 II路径和约束提前剪枝超目标值的分支4.3 常见坑点与避坑指南忘记回溯撤销操作最常见的错误处理节点和回溯撤销必须成对出现否则路径会持续累加导致结果完全错误startIndex 使用错误排列问题无需 startIndex组合 / 子集 / 切割问题必须用 startIndex否则会出现重复结果去重逻辑混淆区分「树层去重」和「树枝去重」绝大多数场景需要的是树层去重同一层不能选重复元素不要搞混数组越界C 语言中要严格控制数组边界提前定义足够的数组长度避免路径、结果数组越界访问递归栈溢出必须明确终止条件避免无限递归同时控制递归深度不要过大。