【代码随想录】【算法训练营】【第27天】 [39]组合总和 [40] 组合总和II [131]分割回文串

前言

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

day26，休息的周末~
day 27，周一，库存没了，哭死~

题目详情

[39] 组合总和

题目描述

39 组合总和

解题思路

前提：组合的子集问题，统一元素可以重复选取
思路：回溯 + 剪枝。
重点：剪枝的前提是数组已排序。

代码实现

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 backtracing(int* candidates, int candidatesSize, int target, int index, int *nums, int numsSize, int ***ans, int* returnSize, int** returnColumnSizes)
{
    // 退出条件
    if (0 == target)
    {
        *ans = (int **)realloc(*ans, sizeof(int *) * ((*returnSize) + 1));
        (*ans)[*returnSize] = (int *)malloc(sizeof(int) * (numsSize));
        for (int i = 0; i < numsSize; i++)
        {
            (*ans)[*returnSize][i] = nums[i];
        }
        *returnColumnSizes = (int *)realloc(*returnColumnSizes, sizeof(int) * ((*returnSize) + 1));
        (*returnColumnSizes)[*returnSize] = numsSize;
        (*returnSize)++;
        return ;
    }
    
    for (int j = index; j < candidatesSize; j++)
    {
        if (target < candidates[j])
        {
            continue ;
        }
        // 递归
        nums[numsSize] = candidates[j];
        numsSize++;
        backtracing(candidates, candidatesSize, target - candidates[j], j, nums, numsSize, ans, returnSize, returnColumnSizes);
        // 回溯
        numsSize--;
        nums[numsSize] = 0;
    }
    return ;
}

int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    // 判空
    if (candidatesSize == 0)
    {
        return NULL;
    }
    // 输出
    int **ans = NULL;
    int nums[41];
    int index = 0;
    *returnSize = 0;
    printf("%d\n", target);
    backtracing(candidates, candidatesSize, target, 0, nums, 0, &ans, returnSize, returnColumnSizes);
    if (*returnSize == 0)
    {
        return NULL;
    }
    return ans;
}

回溯 + 排序 + 剪枝

/**
 * 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().
 */

int cmp(const void *p1, const void *p2)
{
    return *(int *)p1 > *(int *)p2;
}

void backtracing(int* candidates, int candidatesSize, int target, int index, int *nums, int numsSize, int ***ans, int* returnSize, int** returnColumnSizes)
{
    // 退出条件
    if (0 == target)
    {
        *ans = (int **)realloc(*ans, sizeof(int *) * ((*returnSize) + 1));
        (*ans)[*returnSize] = (int *)malloc(sizeof(int) * (numsSize));
        for (int i = 0; i < numsSize; i++)
        {
            (*ans)[*returnSize][i] = nums[i];
        }
        *returnColumnSizes = (int *)realloc(*returnColumnSizes, sizeof(int) * ((*returnSize) + 1));
        (*returnColumnSizes)[*returnSize] = numsSize;
        (*returnSize)++;
        return ;
    }
    
    // 剪枝
    for (int j = index; (j < candidatesSize) && (target >= candidates[j]); j++)
    {
        // 递归
        nums[numsSize] = candidates[j];
        numsSize++;
        backtracing(candidates, candidatesSize, target - candidates[j], j, nums, numsSize, ans, returnSize, returnColumnSizes);
        // 回溯
        numsSize--;
        nums[numsSize] = 0;
    }
    return ;
}

int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    // 判空
    if (candidatesSize == 0)
    {
        return NULL;
    }
    // 排序
    qsort(candidates, candidatesSize, sizeof(int), cmp);
    // 输出
    int **ans = NULL;
    int nums[41];
    int index = 0;
    *returnSize = 0;
    backtracing(candidates, candidatesSize, target, 0, nums, 0, &ans, returnSize, returnColumnSizes);
    if (*returnSize == 0)
    {
        return NULL;
    }
    return ans;
}

[40] 组合总和II

题目描述

40 组合总和II

解题思路

前提：组合的子集问题，同一元素只能使用一次，但是结果不包含重复组合
思路：回溯 + 剪枝
重点：结果子集中排除重复组合，需要树形结构中，同一树层的相同的元素值不可重复选取，使用used数组实现去重。

代码实现

C语言

利用used数组 false，同一树层去重

/**
 * 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().
 */

int cmp(const void *p1, const void *p2)
{
    return *(int *)p1 > *(int *)p2;
}

void backtracing(int* candidates, int candidatesSize, int target, int index, int *nums, int numsSize, bool *used, int ***ans, int* returnSize, int** returnColumnSizes)
{
    // 退出条件
    if (0 == target)
    {
        *ans = (int **)realloc(*ans, sizeof(int *) * ((*returnSize) + 1));
        (*ans)[*returnSize] = (int *)malloc(sizeof(int) * (numsSize));
        for (int i = 0; i < numsSize; i++)
        {
            (*ans)[*returnSize][i] = nums[i];
        }
        *returnColumnSizes = (int *)realloc(*returnColumnSizes, sizeof(int) * ((*returnSize) + 1));
        (*returnColumnSizes)[*returnSize] = numsSize;
        (*returnSize)++;
        return ;
    }
    for (int j = index; (j < candidatesSize) && (target >= candidates[j]); j++)
    {
        // 去重
        if ((j > 0) && (candidates[j] == candidates[j - 1]) && (used[j - 1] == false))
        {
            continue;
        }
        // 递归
        nums[numsSize] = candidates[j];
        used[j] = true;
        numsSize++;
        backtracing(candidates, candidatesSize, target - candidates[j], j + 1, nums, numsSize, used, ans, returnSize, returnColumnSizes);
        // 回溯
        numsSize--;
        used[j] = false;
        nums[numsSize] = 0;
    }
    return ;
}

int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    // 判空
    if (candidatesSize == 0)
    {
        return NULL;
    }
    // 排序
    qsort(candidates, candidatesSize, sizeof(int), cmp);
    // 输出
    int **ans = NULL;
    int nums[100] = {0};
    bool used[100] = {false};
    int index = 0;
    *returnSize = 0;
    backtracing(candidates, candidatesSize, target, 0, nums, 0, used, &ans, returnSize, returnColumnSizes);
    if (*returnSize == 0)
    {
        return NULL;
    }
    return ans;
}