力扣第39题-组合总和
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题-组合总和Ⅱ
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. }
