代码随想录第二十二天（一刷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开始遍历，一直遍历到9for (i = startIndex; i <= 9; i++) {sum += i; // 处理path[pathTop++] = i; // 处理backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndexsum -= 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，所以数组长度要+1char* 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和resultpath = (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;
}