【代码随想录】【算法训练营】【第24天】 [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;
}

今日收获

1. 回溯算法 + 剪枝。