代码随想录第二十二天

回溯算法理论介绍

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

如何理解回溯算法

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

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

递归就要有终止条件，所以必然是一棵高度有限的树（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) 可能返回一个不正确的长度值（可能是过大或过小）。

反思

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