Leecode刷题C语言之组合总和②

 执行结果:通过

执行用时和内存消耗如下：

int** ans;
int* ansColumnSizes;
int ansSize;int* sequence;
int sequenceSize;int** freq;
int freqSize;void dfs(int pos, int rest) {if (rest == 0) {int* tmp = malloc(sizeof(int) * sequenceSize);memcpy(tmp, sequence, sizeof(int) * sequenceSize);ans[ansSize] = tmp;ansColumnSizes[ansSize++] = sequenceSize;return;}if (pos == freqSize || rest < freq[pos][0]) {return;}dfs(pos + 1, rest);int most = fmin(rest / freq[pos][0], freq[pos][1]);for (int i = 1; i <= most; ++i) {sequence[sequenceSize++] = freq[pos][0];dfs(pos + 1, rest - i * freq[pos][0]);}sequenceSize -= most;
}int comp(const void* a, const void* b) {return *(int*)a - *(int*)b;
}int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {ans = malloc(sizeof(int*) * 2001);ansColumnSizes = malloc(sizeof(int) * 2001);sequence = malloc(sizeof(int) * 2001);freq = malloc(sizeof(int*) * 2001);ansSize = sequenceSize = freqSize = 0;qsort(candidates, candidatesSize, sizeof(int), comp);for (int i = 0; i < candidatesSize; ++i) {if (freqSize == 0 || candidates[i] != freq[freqSize - 1][0]) {freq[freqSize] = malloc(sizeof(int) * 2);freq[freqSize][0] = candidates[i];freq[freqSize++][1] = 1;} else {++freq[freqSize - 1][1];}}dfs(0, target);*returnSize = ansSize;*returnColumnSizes = ansColumnSizes;return ans;
}

解题思路：

1. 初始化变量：
   • ans：一个二维数组，用于存储所有符合条件的组合。
   • ansColumnSizes：一个一维数组，用于存储每个组合中元素的数量。
   • ansSize：一个整数，记录当前找到的符合条件的组合数量。
   • sequence：一个一维数组，用于在深度优先搜索（DFS）过程中临时存储当前的组合。
   • sequenceSize：一个整数，记录当前 sequence 数组中的元素数量。
   • freq：一个二维数组，用于存储每个候选数字及其出现的次数。
   • freqSize：一个整数，记录 freq 数组中的元素数量。
2. 排序候选数组：
   • 使用 qsort 函数对候选数组 candidates 进行排序，这是为了确保相同的数字相邻，从而方便后续处理。
3. 处理频率：
   • 遍历排序后的候选数组，将每个不同的数字及其出现次数存储在 freq 数组中。如果当前数字与前一个数字不同，则在 freq 中添加一个新的条目；如果相同，则增加前一个条目的计数。
4. 深度优先搜索（DFS）：
   • dfs 函数是递归函数，用于构建所有符合条件的组合。
   • 参数 pos 表示当前在 freq 数组中处理的位置。
   • 参数 rest 表示当前还需要多少数字之和才能达到目标数 target。
   • 如果 rest 为 0，表示找到了一个符合条件的组合，将其复制到 ans 数组中，并记录该组合的大小。
   • 如果 pos 等于 freqSize 或 rest 小于当前 freq[pos] 的数字，则回溯。
   • 首先尝试不选择当前数字（即，递归调用 dfs(pos + 1, rest)）。
   • 然后计算最多可以选择当前数字的次数（即，rest / freq[pos][0] 的整数部分，但不能超过 freq[pos][1]），并尝试选择这些次数中的每一种（通过循环）。
   • 每次选择一个数字后，递归调用 dfs，同时减少 rest 的值，并更新 sequence 和 sequenceSize。
   • 回溯时，需要恢复 sequenceSize 的值。
5. 返回结果：
   • 将找到的组合数量 ansSize 赋值给 returnSize。
   • 将 ansColumnSizes 赋值给 returnColumnSizes。
   • 返回 ans 数组。

这个算法通过排序和频率处理，以及深度优先搜索中的剪枝（如当 rest 小于当前数字时直接回溯），有效地减少了不必要的搜索，从而提高了效率。