C语言算法-解答组合总和 II问题的C语言实现

题目

给定一个包含重复元素的数组 candidates 和一个目标值 target，找出数组中所有不重复的可以使数字和为目标值的组合。数组中的数字只能在每个组合中使用一次。

引言

组合总和 II问题是一个经典的组合求和问题，与组合总和问题类似，但不同之处在于组合中的每个数字只能使用一次，并且候选数组中可能包含重复的元素。在解决这个问题时，我们需要考虑回溯算法和数组元素的组合逻辑。

算法思路

我们将使用深度优先搜索（DFS）的方法来解决组合总和 II问题。

算法的步骤如下：

1. 首先对候选数组进行排序，这样在后续搜索的过程中可以方便地跳过重复的元素。
2. 定义一个辅助函数 dfs，用于搜索数组中所有可能的组合。在 dfs 函数中，维护一个当前组合的临时数组 temp，和一个当前组合的数字和 sum。
3. 遍历候选数组中的每个数字，将数字添加到 temp 中，并将 sum 加上该数字。
4. 如果 sum 等于目标值 target，将当前组合 temp 添加到结果数组中。
5. 如果 sum 大于目标值 target，说明当前组合已经不满足条件，直接返回。
6. 否则，递归调用 dfs 函数，继续搜索下一个数字，并更新 temp 和 sum。
7. 每次递归完成后，将 temp 中最后一个数字移除，进行回溯操作。

代码实现

下面是使用C语言实现的代码：

#include <stdio.h>
#include <stdlib.h>

void dfs(int* candidates, int candidatesSize, int target, int* temp, int tempSize, int sum, int** result, int* resultSize, int* colSize, int startIndex) {
    if (sum == target) {
        result[*resultSize] = (int*)malloc(tempSize * sizeof(int));
        for (int i = 0; i < tempSize; i++) {
            result[*resultSize][i] = temp[i];
        }
        colSize[*resultSize] = tempSize;
        (*resultSize)++;
        return;
    }

    for (int i = startIndex; i < candidatesSize; i++) {
        if (i > startIndex && candidates[i] == candidates[i - 1]) {
            continue;
        }
        if (sum + candidates[i] <= target) {
            temp[tempSize] = candidates[i];
            dfs(candidates, candidatesSize, target, temp, tempSize + 1, sum + candidates[i], result, resultSize, colSize, i + 1);
        }
    }
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    qsort(candidates, candidatesSize, sizeof(int), compare);

    int** result = (int**)malloc(1000 * sizeof(int*));
    int* colSize = (int*)malloc(1000 * sizeof(int));
    int* temp = (int*)malloc(target * sizeof(int));
    int resultSize = 0;

    dfs(candidates, candidatesSize, target, temp, 0, 0, result, &resultSize, colSize, 0);

    *returnSize = resultSize;
    *returnColumnSizes = colSize;
    return result;
}

int main() {
    int candidates[] = {10, 1, 2, 7, 6, 1, 5};
    int candidatesSize = sizeof(candidates) / sizeof(candidates[0]);
    int target = 8;
    int returnSize;
    int* returnColumnSizes;

    int** result = combinationSum2(candidates, candidatesSize, target, &returnSize, &returnColumnSizes);

    printf("Candidates: ");
    for (int i = 0; i < candidatesSize; i++) {
        printf("%d ", candidates[i]);
    }
    printf("\n");

    printf("Target: %d\n", target);
    printf("Combinations:\n");
    for (int i = 0; i < returnSize; i++) {
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d ", result[i][j]);
        }
        printf("\n");
        free(result[i]);
    }

    free(result);
    free(returnColumnSizes);

    return 0;
}

算法分析

该算法使用了深度优先搜索（DFS）搜索数组中所有可能的组合，所以时间复杂度为 O(S)，其中 S 是所有可行解的长度之和。在最坏的情况下，可行解的长度为 target 的指数级别，所以时间复杂度为 O(2^n)。

空间复杂度为 O(target)，算法使用了临时数组 temp 和结果数组 result。

示例和测试

示例输入:

Candidates: 10 1 2 7 6 1 5
Target: 8

示例输出:

Combinations:
1 1 6 
1 2 5 
1 7 
2 6 

总结

本文使用C语言实现了解答组合总和 II问题的代码。通过使用深度优先搜索（DFS）搜索数组中所有可能的组合，我们能够找到数组中所有不重复的可以使数字和为目标值的组合。该算法的时间复杂度为 O(2^n)，空间复杂度为 O(target)。