代码随想录第二十二天

回溯算法理论介绍

回溯算法是一种基于递归思想的算法设计技术，适用于解决需要构造所有解或找到特定解的组合问题。回溯的基本思路是通过系统地搜索所有可能的解决方案，然后逐步撤销不符合要求的选择，回到上一步继续尝试。这种算法最适合应用于决策树、排列组合、子集生成等涉及多阶段决策问题的场景。

如何理解回溯算法

回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

回溯算法的一般结构

void backtrack(参数) {if (满足结束条件) {记录解或返回;}for (选择 in 可选择列表) {做出选择;backtrack(新的参数); // 递归调用继续做下一步选择撤销选择;  // 撤销选择，回到上一步的状态}
}

剪枝套路

剪枝（Pruning）是一种优化回溯算法的技术，用于在搜索过程中减小问题规模、提高效率，从而避免不必要的计算。它的核心思想是：在构造解决方案的过程中，如果发现某些部分已经不能通向一个可行的解，就可以提前结束这条路径的搜索，直接“剪掉”这部分的搜索空间，从而节省时间。

简单来说，剪枝就是在回溯过程中“提前发现死胡同”，然后立刻停止当前的搜索，而不是继续探索下去。这样可以减少不必要的计算量，极大地提高回溯的效率。

77.组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

• 1 <= n <= 20
• 1 <= k <= n

思路：

最开始的思路就是按照回溯算法的模板写的，这道题的目的是从范围 [1, n] 中选取 k 个数，生成所有可能的组合，并返回这些组合。解决这道题的有效方法是使用回溯算法。回溯的基本思路是逐步尝试所有可能的选择，并通过递归进行深度优先搜索。在每次递归过程中，我们依次选择一个新的数字加入当前组合，如果当前组合的大小达到了 k，就将其存储为一个有效解。在这之后，我们会通过回溯（撤销选择的方式返回到上一步，尝试其他可能的选择，从而确保找到所有的组合解。为了优化算法，我们应用了剪枝策略，即在递归过程中，如果剩余的可选数字数量不足以组成完整的组合，我们会提前终止当前路径，从而减少不必要的计算，提高效率。通过这种逐步尝试、回退、剪枝的过程，最终生成并返回所有符合要求的组合。

解答：

第一次尝试(超出内存范围)

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
void travelback(int n,int k,int start,int* num,int combinesize,int*** result,int* returnSize,int** returnColumnSizes)
{if(combinesize == k){(*returnSize)++;*result = realloc(*result,(*returnSize)*sizeof(int*));(*result)[(*returnSize)-1] = malloc(sizeof(int)*k);for(int i = 0;i < k;i++){(*result)[(*returnSize)-1][i] = num[i];}*returnColumnSizes = realloc(*returnColumnSizes,(*returnSize)*sizeof(int));(*returnColumnSizes)[(*returnSize)-1] = k;return;}for(int i = start;i <= n;i++){num[combinesize] = i;travelback(n,k,i+1,num,combinesize+1,result,returnSize,returnColumnSizes);}
}
int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {*returnSize = 0;*returnColumnSizes = NULL;int** result = NULL;int* num = malloc(sizeof(int)*k);travelback(n,k,1,num,0,&result,returnSize,returnColumnSizes);return result;
}

最终答案(gpt帮助)

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
long long factorial(int n) {long long result = 1;for (int i = 1; i <= n; i++) {result *= i;}return result;
}
int combinationCount(int n, int k) {return factorial(n) / (factorial(k) * factorial(n - k));
}
void travelback(int n, int k, int start, int* num, int combinesize, int** result, int* returnSize) {if (combinesize == k) {for (int i = 0; i < k; i++) {result[*returnSize][i] = num[i];}(*returnSize)++;return;}for (int i = start; i <= n; i++) {num[combinesize] = i;travelback(n, k, i + 1, num, combinesize + 1, result, returnSize);}
}
int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {*returnSize = 0;int totalCombinations = combinationCount(n, k);int** result = malloc(totalCombinations * sizeof(int*));for (int i = 0; i < totalCombinations; i++) {result[i] = malloc(k * sizeof(int));}*returnColumnSizes = malloc(totalCombinations * sizeof(int));for (int i = 0; i < totalCombinations; i++) {(*returnColumnSizes)[i] = k;}int* num = malloc(k * sizeof(int));travelback(n, k, 1, num, 0, result, returnSize);free(num);return result;
}

216.组合总和 |||

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

• 2 <= k <= 9
• 1 <= n <= 60

思路：

这道题与上面很像，但是这道题多了一点条件，所以我们在终止条件下要分成两个部分，当它找的元素已经有要求的那么多个的时候，我们对其进行检测，如果最终结果等于它所要求的结果，那么这是我们需要取得一个数组，如果不是直接返回出去，而我们在取值上面也有变化，我们有一个变量叫做sum是用来进行计算总和的，我们先把这个数值加上，如果不满足的话我们又重新剪掉，最终返回答案。

解答：

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
void travelback(int k,int n,int start,int* num,int combinesize,int*** result,int* returnSize,int** returnColumnSizes,int sum)
{if(combinesize == k){if(sum == n){(*returnSize)++;*result = realloc(*result,(*returnSize)*sizeof(int*));(*result)[(*returnSize)-1] = malloc(sizeof(int)*k);for(int i = 0;i < k;i++){(*result)[(*returnSize)-1][i] = num[i];}*returnColumnSizes = realloc(*returnColumnSizes,(*returnSize)*sizeof(int));(*returnColumnSizes)[(*returnSize)-1] = k;}return;}for(int i = start;i <= 9;i++){sum += i;num[combinesize] = i;travelback(k,n,i+1,num,combinesize+1,result,returnSize,returnColumnSizes,sum);sum -= i;}
}
int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes) {*returnSize = 0;*returnColumnSizes = NULL;int** result = NULL;int* num = malloc(sizeof(int)*k);int sum = 0;travelback(k,n,1,num,0,&result,returnSize,returnColumnSizes,sum);return result;
}

17.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

1	2 abc	3 def
4 ghi	5 jkl	6 mno
7 pqrs	8 tuv	9 wxyz
*+	0 -	# ↑

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

思路：

解答：

/*** Note: The returned array must be malloced, assume caller calls free().*/
void travelback(const char* digits, int* returnSize, const char** a, int index, char** result, char* num) {if (index == strlen(digits)) {num[index] = '\0';  result[(*returnSize)] = malloc((strlen(num) + 1) * sizeof(char)); strcpy(result[*returnSize], num);(*returnSize)++;return;}int digit = digits[index] - '0';const char* letter = a[digit];for (int i = 0; i < strlen(letter); i++) {num[index] = letter[i];travelback(digits, returnSize, a, index + 1, result, num);}
}
char** letterCombinations(char* digits, int* returnSize) {const char* a[10] = {" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};if (digits == NULL || strlen(digits) == 0) {*returnSize = 0;return NULL;}int len = strlen(digits);int maxSize = 1;for (int i = 0; i < len; i++) {int digit = digits[i] - '0';if (digit >= 2 && digit <= 9) {maxSize *= strlen(a[digit]);}}*returnSize = 0;char* num = (char*)malloc((len + 1) * sizeof(char)); char** result = (char**)malloc(maxSize * sizeof(char*));travelback(digits, returnSize, a, 0, result, num);free(num); return result;
}

注意：

num[index] = '\0’一定要放在最上面，因为调用 malloc((strlen(num) + 1) * sizeof(char)) 的时候，num 并不是一个完整的字符串，因为 num[index] = '\0'; 还没有设置。strlen(num) 计算长度时会从 num 的开头开始寻找 '\0'，但由于它还未设置，因此 strlen(num) 可能返回一个不正确的长度值（可能是过大或过小）。

反思

今天的题目很有难度，有些题目需要多次理解，但是今天对于回溯算法有了一定的理解，还需要多练。