力扣第39题-组合总和
2026.3.10
1.本题是经典的回溯算法题目，要用到递归算法，进行深度搜索。简单来说，回溯算法就是一种“暴力检索+剪枝”的算法，每一步都会进行尝试，如果不行或者寻找到答案就剪枝，并撤回本次选择。
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而非i+1 → 允许重复选取当前元素 46. backTrack(i, candidates, candidatesSize, target); 47. // 回溯：撤销选择，路径长度-1（path的值无需清空，下一次循环会覆盖） 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. // 为当前组合分配独立内存（不能直接用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. 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而非i+1 → 允许重复选取当前元素 58. backTrack(i, candidates, candidatesSize, target); 59. // 回溯：撤销选择，路径长度-1（path的值无需清空，下一次循环会覆盖） 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.10
1.这题和力扣第39题极为相似，都是使用回溯算法进行深度搜索，不同的两点是这次要找的接组合不能同一个元素用多次，以及组合中不能有重复的情况。初步设想是在每次for循环调用回溯函数的时候从start+1开始，类似如下代码：
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的初始值会变为0+1=1，没有完整遍历整个数组，正确的做法是不改变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. // i>start：保证是「同层」重复（而非跨层） 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. // 递归传i+1（而非i）：下一层只能从i+1开始选，当前元素不会被重复选 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.9
1.今天又回顾了这道题，对于回溯函数中去除重复元素的部分需要额外注意，刚开始直接写成了if (i < candidatesSize - 1 && candidates[i] == candidates[i + 1])，这种写法是将所有重复元素都跳过了。而正确的写法是if (i > start && candidates[i] == candidates[i - 1])，i > start可以保证每一树层的第一个元素一定会被取到，即使它在整个candidates数组中不是第一次出现的，但它满足在本层中是第一次出现的，也是可以选取的。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
