代码随想录第二十二天（一刷C语言）|组合总数电话号码的字母组合

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

一、组合总数

思路：参考carl文档和视频

1、需要一维数组path来存放符合条件的结果，二维数组result来存放结果集。

2、targetSum 目标和，也就是题目中的n。

3、k 就是题目中要求k个数的集合。

4、sum 为已经收集的元素的总和，也就是path里元素的总和。

5、startIndex 为下一层for循环搜索的起始位置。

ledcode题目：https://leetcode.cn/problems/combination-sum-iii/description/

AC代码：

int* path;
int pathTop;
int** ans;
int ansTop;

void backtracking(int targetSum, int k, int sum, int startIndex) {
    if(pathTop == k) {
        if(sum == targetSum) {
            int* tempPath = (int*)malloc(sizeof(int) * k);
            int j;
            for(j = 0; j < k; j++)
                tempPath[j] = path[j];
            ans[ansTop++] = tempPath;
        }
        return;
    }
    int i;
    //从startIndex开始遍历，一直遍历到9
    for (i = startIndex; i <= 9; i++) {
        sum += i; // 处理
        path[pathTop++] = i; // 处理
        backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
        sum -= i; // 回溯
        pathTop--;; // 回溯
    }
}

int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes){
    //初始化辅助变量
    path = (int*)malloc(sizeof(int) * k);
    ans = (int**)malloc(sizeof(int*) * 20);
    pathTop = ansTop = 0;

    backtracking(n, k, 0, 1);

    //设置返回的二维数组中元素个数为ansTop
    *returnSize = ansTop;
    //设置二维数组中每个元素个数的大小为k
    *returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
    int i;
    for(i = 0; i < ansTop; i++) {
        (*returnColumnSizes)[i] = k;
    }
    return ans;
}

二、电话号码的字母组合

思路：参考carl文档和视频

1、定义一个二维数组，例如：string letterMap[10]，来做映射。

2、用回溯法解决n个for循环问题

3、需要一个字符串s来收集叶子节点的结果，然后用一个字符串数组result保存起来

lecode题目：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/

AC代码：

char* path;
int pathTop;
char** result;
int resultTop;
char* letterMap[10] = {"", //0
        "", //1
        "abc", //2
        "def", //3
        "ghi", //4
        "jkl", //5
        "mno", //6
        "pqrs", //7
        "tuv", //8
        "wxyz", //9
};
void backTracking(char* digits, int index) {
    //若当前下标等于digits数组长度
    if(index == strlen(digits)) {
        //复制digits数组，因为最后要多存储一个0，所以数组长度要+1
        char* tempString = (char*)malloc(sizeof(char) * strlen(digits) + 1);
        int j;
        for(j = 0; j < strlen(digits); j++) {
            tempString[j] = path[j];
        }
        //char数组最后要以0结尾
        tempString[strlen(digits)] = 0;
        result[resultTop++] = tempString;
        return ;
    }
    //将字符数字转换为真的数字
    int digit = digits[index] - '0';
    //找到letterMap中对应的字符串
    char* letters = letterMap[digit];
    int i;
    for(i = 0; i < strlen(letters); i++) {
        path[pathTop++] = letters[i];
        //递归，处理下一层数字
        backTracking(digits, index+1);
        pathTop--;
    }
}

char ** letterCombinations(char * digits, int* returnSize){
    //初始化path和result
    path = (char*)malloc(sizeof(char) * strlen(digits));
    result = (char**)malloc(sizeof(char*) * 300);

    *returnSize = 0;
    //若digits数组中元素个数为0，返回空集
    if(strlen(digits) == 0) 
        return result;
    pathTop = resultTop = 0;
    backTracking(digits, 0);
    *returnSize = resultTop;

    return result;
}