代码随想录第二十一天（一刷C语言）|回溯算法组合

创作目的：为了方便自己后续复习重点，以及养成写博客的习惯。

一、回溯算法

1、种类

排列、组合、分割、子集、棋盘问题

2、回溯步骤

（0）回溯抽象

回溯法解决的问题均可以抽象为树形结构（N叉树）

（1）回溯函数模板返回值以及参数

函数返回值一般为void，回溯算的参数一般是先写逻辑，然后需要什么参数，就填什么参数。

（2）回溯函数终止条件

if(条件成立) {
    存放结果;
    return;
}

（3）回溯搜索的遍历过程

回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

3、与递归对比和效率

回溯与递归方法和步骤类似，回溯是暴力查找，效率不高。

二、组合

思路：C解法参考了ledcode官方题解

lecode题目：https://leetcode.cn/problems/combinations/

AC代码：

int* temp;
int tempSize;

int** ans;
int ansSize;

void dfs(int cur, int n, int k) {
    // 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
    if (tempSize + (n - cur + 1) < k) {
        return;
    }
    // 记录合法的答案
    if (tempSize == k) {
        int* tmp = malloc(sizeof(int) * k);
        for (int i = 0; i < k; i++) {
            tmp[i] = temp[i];
        }
        ans[ansSize++] = tmp;
        return;
    }
    // 考虑选择当前位置
    temp[tempSize++] = cur;
    dfs(cur + 1, n, k);
    tempSize--;
    // 考虑不选择当前位置
    dfs(cur + 1, n, k);
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {
    temp = malloc(sizeof(int) * k);
    ans = malloc(sizeof(int*) * 200001);
    tempSize = ansSize = 0;
    dfs(1, n, k);
    *returnSize = ansSize;
    *returnColumnSizes = malloc(sizeof(int) * ansSize);
    for (int i = 0; i < ansSize; i++) {
        (*returnColumnSizes)[i] = k;
    }
    return ans;
}