力扣第39题-组合总和2026.3.101.本题是经典的回溯算法题目要用到递归算法进行深度搜索。简单来说回溯算法就是一种“暴力检索剪枝”的算法每一步都会进行尝试如果不行或者寻找到答案就剪枝并撤回本次选择。2.对于回溯算法有一套固定的模板即①确定递归函数参数全局变量/入参②确定终止条件找到结果/走不通③遍历选择集尝试所有可能的选择a. 做出选择加入路径b. 递归深入下一层c. 撤销选择回溯移除路径最后一个元素可以总结出如下通用模板1. // 全局辅助变量可选简化参数 2. int* path; // 当前路径正在构建的解决方案 3. int pathSize; // 当前路径长度 4. int** result; // 最终结果集 5. int resultSize; // 结果集数量 6. 7. // 回溯核心函数 8. void backtrack(参数列表) { 9. // 1. 终止条件找到有效结果 或 走不通剪枝 10. if (终止条件) { 11. // 记录结果拷贝path到result 12. result[resultSize] 拷贝后的路径; 13. return; // 结束当前递归分支 14. } 15. 16. // 2. 遍历所有可能的选择 17. for (int i 起始索引; i 选择集长度; i) { 18. // 剪枝可选提前排除无效选择减少递归 19. if (当前选择无效) continue/break; 20. 21. // 3. 做出选择将当前元素加入路径 22. path[pathSize] 选择集[i]; 23. 24. // 4. 递归深入下一层注意参数比如是否允许重复选/是否去重 25. backtrack(更新后的参数); 26. 27. // 5. 撤销选择回溯移除最后一个元素 28. pathSize--; 29. } 30. } 31. 32. // 主函数入口 33. int** mainFunction(问题参数, int* returnSize, int** returnColumnSizes) { 34. // 初始化全局变量 35. pathSize 0; 36. resultSize 0; 37. // 分配内存 38. path malloc(...); 39. result malloc(...); 40. 41. // 调用回溯函数 42. backtrack(初始参数); 43. 44. // 处理返回值 45. *returnSize resultSize; 46. *returnColumnSizes 分配并拷贝列数; 47. return result; 48. }3.基于以上思想写出的代码如下1. /** 2. * Return an array of arrays of size *returnSize. 3. * The sizes of the arrays are returned as *returnColumnSizes array. 4. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). 5. */ 6. 7. // 全局辅助变量用于回溯过程中存储临时数据避免函数参数过多 8. int* path; // 存储当前正在构建的组合路径比如[2,2] 9. int pathSize; // path数组的有效元素个数当前路径长度 10. int* col; // 临时存储每个符合条件组合的长度比如[3,1] 11. int resultSize; // 最终结果集中的组合数量 12. int** result; // 最终结果集二维数组存储所有符合条件的组合 13. 14. void backTrack(int start, int* candidates, int candidatesSize, int target){ 15. // 1. 计算当前路径的元素总和 16. int sum 0; 17. for (int i 0; i pathSize; i){ 18. sum path[i]; // 累加path中已选元素的和 19. } 20. 21. // 2. 终止条件1当前路径和等于目标值 → 找到有效组合 22. if (sum target){ 23. // 为当前组合分配独立内存不能直接用path因为path会被回溯修改 24. int* tmp (int*)malloc(sizeof(int) * pathSize); 25. // 把path中的元素拷贝到新内存中 26. for (int i 0; i pathSize; i){ 27. tmp[i] path[i]; 28. } 29. // 将该组合加入结果集 30. result[resultSize] tmp; 31. // 记录该组合的长度并将结果集计数1 32. col[resultSize] pathSize; 33. return; // 找到组合返回上层递归 34. } 35. 36. // 3. 终止条件2当前路径和超过目标值 → 剪枝无需继续递归 37. if (sum target){ 38. return; 39. } 40. 41. // 4. 遍历候选数组核心从start开始避免重复组合 42. for (int i start; i candidatesSize; i){ 43. // 选择当前元素将candidates[i]加入路径路径长度1 44. path[pathSize] candidates[i]; 45. // 递归传入i而非i1 → 允许重复选取当前元素 46. backTrack(i, candidates, candidatesSize, target); 47. // 回溯撤销选择路径长度-1path的值无需清空下一次循环会覆盖 48. pathSize--; 49. } 50. } 51. 52. int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) { 53. // 1. 初始化全局变量重置状态避免多次调用时数据残留 54. resultSize 0; 55. pathSize 0; 56. 57. // 2. 分配内存预估最大容量题目保证组合数≤150 58. result (int**)malloc(sizeof(int*) * 150); // 结果集最多存150个组合 59. path (int*)malloc(sizeof(int) * target); // 路径最坏情况全选1最多target个元素 60. col (int*)malloc(sizeof(int) * 150); // 临时存储每个组合的长度 61. 62. // 3. 调用回溯函数从第0个元素开始遍历 63. backTrack(0, candidates, candidatesSize, target); 64. 65. // 4. 设置输出参数符合题目要求 66. *returnSize resultSize; // 返回组合的总数量 67. // 为返回的列数数组分配内存仅分配实际需要的大小 68. *returnColumnSizes (int*)malloc(sizeof(int) * resultSize); 69. // 把临时存储的组合长度拷贝到输出数组中 70. for (int i 0; i resultSize; i){ 71. (*returnColumnSizes)[i] col[i]; 72. } 73. 74. // 5. 返回最终结果集 75. return result; 76. }4.注意到写出的代码没有进行qsort排序也能通过询问了ai只是得知对于回溯算法排序不是刚需但会影响运行效率。如果不排序算法会遍历所有的路径来寻找可能组合如果排序可以进行提前剪枝来减少无用递归调用。以官方给出的数组[2, 3, 6 ,7]target 7为例当递归到第三次2时此时sum 6再递归一次2就会大于target如果不进行优化的话代码还会遍历后续的3, 6, 7而如果提前进行剪枝的话就会直接break跳过本次搜寻。5.提前剪枝的核心代码如下1. if (sum candidates[i] target) { 2. break; 3. }以下是优化后的完整代码1. /** 2. * Return an array of arrays of size *returnSize. 3. * The sizes of the arrays are returned as *returnColumnSizes array. 4. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). 5. */ 6. 7. // 全局辅助变量用于回溯过程存储临时数据避免函数参数过多 8. int* path; // 存储当前正在构建的组合路径例如[2,2] 9. int pathSize; // path数组的有效元素个数当前路径长度 10. int* col; // 临时存储每个符合条件组合的长度例如[3,1] 11. int resultSize; // 最终结果集中的组合数量 12. int** result; // 最终结果集二维数组存储所有符合条件的组合 13. 14. int cmp(const void* a, const void* b){ 15. return *(int*)a - *(int*)b; 16. } 17. 18. void backTrack(int start, int* candidates, int candidatesSize, int target){ 19. // 1. 计算当前路径的元素总和遍历path累加 20. int sum 0; 21. for (int i 0; i pathSize; i){ 22. sum path[i]; 23. } 24. 25. // 2. 终止条件1当前路径和等于目标值 → 找到有效组合 26. if (sum target){ 27. // 为当前组合分配独立内存不能直接用pathpath会被回溯修改 28. int* tmp (int*)malloc(sizeof(int) * pathSize); 29. // 拷贝path中的元素到新内存 30. for (int i 0; i pathSize; i){ 31. tmp[i] path[i]; 32. } 33. // 将该组合加入结果集 34. result[resultSize] tmp; 35. // 记录该组合的长度并将结果集计数1 36. col[resultSize] pathSize; 37. return; // 找到组合返回上层递归 38. } 39. 40. // 3. 终止条件2当前路径和超过目标值 → 剪枝无需继续递归 41. if (sum target){ 42. return; 43. } 44. 45. // 4. 遍历候选数组从start开始避免重复组合 46. for (int i start; i candidatesSize; i){ 47. // 核心剪枝逻辑 48. // 排序后数组升序sum 当前元素 target → 后续元素更大直接终止循环 49. // 作用提前跳过所有无效递归大幅减少计算量 50. if (sum candidates[i] target){ 51. break; 52. } 53. // 54. 55. // 选择当前元素将candidates[i]加入路径路径长度1 56. path[pathSize] candidates[i]; 57. // 递归传入i而非i1 → 允许重复选取当前元素 58. backTrack(i, candidates, candidatesSize, target); 59. // 回溯撤销选择路径长度-1path的值无需清空下一次循环会覆盖 60. pathSize--; 61. } 62. } 63. 64. int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) { 65. // 1. 初始化全局变量重置状态避免多次调用时数据残留 66. resultSize 0; 67. pathSize 0; 68. 69. // 2. 分配内存预估最大容量题目保证组合数≤150 70. result (int**)malloc(sizeof(int*) * 150); // 结果集最多存150个组合 71. path (int*)malloc(sizeof(int) * target); // 路径最坏情况全选1最多target个元素 72. col (int*)malloc(sizeof(int) * 150); // 临时存储每个组合的长度 73. 74. // 3. 对候选数组排序为提前剪枝做准备核心前提 75. qsort(candidates, candidatesSize, sizeof(int), cmp); 76. 77. // 4. 调用回溯函数从第0个元素开始遍历 78. backTrack(0, candidates, candidatesSize, target); 79. 80. // 5. 设置输出参数符合题目要求 81. *returnSize resultSize; // 返回组合的总数量 82. // 为返回的列数数组分配内存仅分配实际需要的大小 83. *returnColumnSizes (int*)malloc(sizeof(int) * resultSize); 84. // 把临时存储的组合长度拷贝到输出数组中 85. for (int i 0; i resultSize; i){ 86. (*returnColumnSizes)[i] col[i]; 87. } 88. 89. // 6. 返回最终结果集 90. return result; 91. }6.既然有了提前剪枝的操作代码里的兜底剪枝函数是否能删除可以删但建议保留因为兜底剪枝的代码是回溯算法的标配。力扣第40题-组合总和Ⅱ2026.3.101.这题和力扣第39题极为相似都是使用回溯算法进行深度搜索不同的两点是这次要找的接组合不能同一个元素用多次以及组合中不能有重复的情况。初步设想是在每次for循环调用回溯函数的时候从start1开始类似如下代码1. for (int i start 1; i candidatesSize; i){ 2. } 3. if (sum candidates[i] target){ 4. break; 5. } 6. path[pathSize] candidates[i]; 7. backTrack(i, candidates, candidatesSize, target); 8. pathSize--; 9. }但这种解法是错误的因为for循环中i的初始值会变为011没有完整遍历整个数组正确的做法是不改变i start在每次调用回溯函数的时候传递i 1进去即可。2.现在还需要考虑重复组合的情况只需要在每次for循环中加入重复值判断即可如果重复就跳过本次循环代码如下1. if (i start candidates[i] candidates[i-1]) { 2. continue; 3. }3.其他部分的代码与力扣39题相比没有太多变化完整代码如下1. /** 2. * Return an array of arrays of size *returnSize. 3. * The sizes of the arrays are returned as *returnColumnSizes array. 4. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). 5. */ 6. 7. // 全局辅助变量存储回溯过程的临时数据 8. int* path; // 当前正在构建的组合路径如[1,1,6] 9. int pathSize; // path数组的有效元素个数当前路径长度 10. int* col; // 临时存储每个有效组合的长度如[3,3,2] 11. int** result; // 最终结果集二维数组存储所有符合条件的组合 12. int resultSize; // 结果集中的组合数量 13. 14. int cmp(const void* a, const void* b){ 15. return *(int*)a - *(int*)b; 16. } 17. 18. void backTrack(int start, int* candidates, int candidatesSize, int target){ 19. // 1. 计算当前路径的元素总和 20. int sum 0; 21. for (int i 0; i pathSize; i){ 22. sum path[i]; 23. } 24. 25. // 2. 终止条件1找到和为target的有效组合 26. if (sum target){ 27. // 为当前组合分配独立内存避免共用path数组path会被回溯修改 28. int* tmp (int*)malloc(sizeof(int) * pathSize); 29. // 拷贝path中的元素到新内存 30. for (int i 0; i pathSize; i){ 31. tmp[i] path[i]; 32. } 33. // 将该组合加入结果集 34. result[resultSize] tmp; 35. // 记录该组合的长度结果集计数1 36. col[resultSize] pathSize; 37. } 38. 39. // 3. 终止条件2当前和超过target → 剪枝兜底直接返回 40. if (sum target){ 41. return; 42. } 43. 44. // 4. 遍历候选数组从start开始控制元素仅用一次 45. for (int i start; i candidatesSize; i){ 46. // 核心1同层去重 47. // istart保证是「同层」重复而非跨层 48. // candidates[i]candidates[i-1]相同值的元素相邻排序的作用 49. // 作用避免生成[1(第一个),2,5]和[1(第二个),2,5]这种重复组合 50. if (i start candidates[i] candidates[i-1]) { 51. continue; 52. } 53. // 54. 55. // 核心2提前剪枝 56. // 排序后sum当前元素target → 后续元素更大直接终止循环 57. if (sum candidates[i] target){ 58. break; 59. } 60. // 61. 62. // 选择当前元素加入路径路径长度1 63. path[pathSize] candidates[i]; 64. // 核心3限制元素仅用一次 65. // 递归传i1而非i下一层只能从i1开始选当前元素不会被重复选 66. backTrack(i 1, candidates, candidatesSize, target); 67. // 68. // 回溯撤销选择路径长度-1 69. pathSize--; 70. } 71. } 72. 73. int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) { 74. // 初始化全局变量重置状态避免多次调用数据残留 75. pathSize 0; 76. resultSize 0; 77. 78. // 1. 排序为「同层去重」和「提前剪枝」做准备核心前提 79. qsort(candidates, candidatesSize, sizeof(int), cmp); 80. 81. // 2. 分配内存预估最大容量避免频繁扩容 82. result (int**)malloc(sizeof(int*) * 10000); // 结果集最多存10000个组合 83. path (int*)malloc(sizeof(int) * target); // 路径最坏情况全选1最多target个元素 84. col (int*)malloc(sizeof(int) * 10000); // 临时存储每个组合的长度 85. 86. // 3. 调用回溯函数从第0个元素开始遍历 87. backTrack(0, candidates, candidatesSize, target); 88. 89. // 4. 设置输出参数符合题目要求 90. *returnSize resultSize; // 返回组合的总数量 91. // 为返回的列数数组分配内存仅分配实际需要的大小 92. *returnColumnSizes (int*)malloc(sizeof(int) * resultSize); 93. // 拷贝临时存储的组合长度到输出数组 94. for (int i 0; i resultSize; i){ 95. (*returnColumnSizes)[i] col[i]; 96. } 97. 98. // 5. 返回最终结果集 99. return result; 100. }2026.7.91.今天又回顾了这道题对于回溯函数中去除重复元素的部分需要额外注意刚开始直接写成了if (i candidatesSize - 1 candidates[i] candidates[i 1])这种写法是将所有重复元素都跳过了。而正确的写法是if (i start candidates[i] candidates[i - 1])i start可以保证每一树层的第一个元素一定会被取到即使它在整个candidates数组中不是第一次出现的但它满足在本层中是第一次出现的也是可以选取的。