【代码随想录】【算法训练营】【第25天】 [216]组合总和III [17] 电话号码的字母组合

前言

思路及算法思维，指路代码随想录。
题目来自 LeetCode。

day 25，周六，坚持有点困难~

题目详情

[216] 组合总和III

题目描述

216 组合总和III

解题思路

前提：组合子集问题
思路：回溯算法，剪枝操作。
重点：回溯算法 + 剪枝。

代码实现

C语言

回溯剪枝

/*** 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 backtracking(int n, int k, int startIndex, int *nums, int *numsSize, int ***ans,  int *returnSize, int **returnColumnSizes)
{if ((n == 0) && (k == *numsSize)){// 找到组合*ans = (int **)realloc(*ans, sizeof(int *) * (*returnSize + 1));*returnColumnSizes = (int *)realloc(*returnColumnSizes, sizeof(int) * (*returnSize + 1));(*ans)[*returnSize] = (int *)malloc(sizeof(int) * k);(*returnColumnSizes)[*returnSize] = k;for (int i = 0; i < k; i++){(*ans)[*returnSize][i] = nums[i];}(*returnSize)++;return ;}// 递归, 剪枝操作for (startIndex; startIndex <= (10 - (k - *numsSize)); startIndex++){// 判断当前合值是否超出if ((n - startIndex) < 0){break;}nums[*numsSize] = startIndex;(*numsSize)++;backtracking(n - startIndex, k, startIndex + 1, nums, numsSize, ans, returnSize, returnColumnSizes);// 回溯(*numsSize)--;}return ;
}int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes) {int **ans = NULL;*returnSize = 0;*returnColumnSizes = NULL;int nums[10];int numsSize = 0;backtracking(n, k, 1, nums, &numsSize, &ans, returnSize,returnColumnSizes);return ans;
}

[17] 电话号码的字母组合

题目描述

17 电话号码的字母组合

解题思路

前提：多个组合取子集问题
思路：回溯算法。
重点：回溯算法。

代码实现

C语言

回溯剪枝

/*** Note: The returned array must be malloced, assume caller calls free().*/
#include <string.h>const char change[8][4] = {{'a', 'b', 'c'}, {'d', 'e', 'f'}, \{'g', 'h', 'i'}, {'j', 'k', 'l'}, {'m', 'n', 'o'}, \{'p', 'q', 'r', 's'}, {'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}};
const int changeNums[8] = {3, 3, 3, 3, 3, 4, 3, 4};void backtracking(char *digits, int startIdx, char *string, int *stringlen, int *returnSize, char ***ans) {if (*stringlen == strlen(digits)) {// 判空if (*stringlen == 0){return ;}// 找到组合*ans = (char **)realloc(*ans, sizeof(char *) * (*returnSize + 1));(*ans)[*returnSize] = (char *)malloc(sizeof(char) * (startIdx + 1));// 输出结果赋值for (int i = 0; i < startIdx; i++) {(*ans)[*returnSize][i] = string[i];}(*ans)[*returnSize][startIdx] = '\0';(*returnSize)++;return;}// 递归, 由于每次从另一组合中获取元素, 故无法剪枝for (int f = 0; f < changeNums[digits[startIdx] - '0' - 2]; f++) {string[*stringlen] = change[digits[startIdx] - '0' - 2][f];(*stringlen)++;backtracking(digits, startIdx + 1, string, stringlen, returnSize, ans);// 回溯(*stringlen)--;string[*stringlen] = '\0';}return ;
}char** letterCombinations(char* digits, int* returnSize) {char **ans = NULL;*returnSize = 0;char string[5];int stringlen = 0;backtracking(digits, 0, string, &stringlen, returnSize, &ans);return ans;
}