长沙网站设计咨询电话,阿土伯 是做网站的吗,wordpress登陆后缀,漳州网站建设公司首选公司力扣第39题#xff1a;组合总和#xff08;C语言解法#xff09;
题目描述
在一个无重复元素的数组 candidates 中找到所有和为目标值 target 的组合。数组中的数字可以多次使用#xff0c;且组合中的元素按非递减顺序排列。
示例#xff1a;
输入#xff1a;candida…力扣第39题组合总和C语言解法
题目描述
在一个无重复元素的数组 candidates 中找到所有和为目标值 target 的组合。数组中的数字可以多次使用且组合中的元素按非递减顺序排列。
示例
输入candidates [2,3,6,7], target 7
输出[[7],[2,2,3]]
解释7 可以由 [7] 或 [2,2,3] 组合得到。注意
所有输入的数字是正整数。结果中的每个组合按非递减顺序排列。
解题思路
本题的关键是找出所有可能的组合可以通过回溯法来解决。回溯的核心是
从每个元素开始尝试将其加入当前组合并递归计算剩余的目标值。如果目标值为 0说明找到了一个合法组合如果小于 0则当前组合无效回溯到上一层。每次递归结束后移除最近加入的数字尝试新组合。
思路步骤
初始化结果数组用于存储所有组合。使用回溯函数递归生成所有组合 如果 target 为 0将当前组合加入结果。如果 target 小于 0返回上一层递归。对每个数字递归加入到组合中继续递归并传递剩余目标值。 最终返回包含所有组合的结果数组。
C语言代码实现
#include stdio.h
#include stdlib.h// 定义动态数组用于存储结果
typedef struct {int** data;int* columnSizes;int size;int capacity;
} ResultArray;// 初始化结果数组
ResultArray* createResultArray() {ResultArray* result (ResultArray*)malloc(sizeof(ResultArray));result-data (int**)malloc(100 * sizeof(int*));result-columnSizes (int*)malloc(100 * sizeof(int));result-size 0;result-capacity 100;return result;
}// 将组合添加到结果数组中
void addResult(ResultArray* result, int* combination, int length) {if (result-size result-capacity) {result-capacity * 2;result-data (int**)realloc(result-data, result-capacity * sizeof(int*));result-columnSizes (int*)realloc(result-columnSizes, result-capacity * sizeof(int));}result-data[result-size] (int*)malloc(length * sizeof(int));for (int i 0; i length; i) {result-data[result-size][i] combination[i];}result-columnSizes[result-size] length;result-size;
}// 回溯函数
void backtrack(int* candidates, int candidatesSize, int target, int* combination, int length, int start, ResultArray* result) {if (target 0) { // 找到一个组合addResult(result, combination, length);return;}if (target 0) return; // 当前组合无效for (int i start; i candidatesSize; i) {combination[length] candidates[i];backtrack(candidates, candidatesSize, target - candidates[i], combination, length 1, i, result);}
}// 主函数组合总和
int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {ResultArray* result createResultArray();int* combination (int*)malloc(target * sizeof(int)); // 存储单个组合// 调用回溯函数backtrack(candidates, candidatesSize, target, combination, 0, 0, result);// 设置返回值*returnSize result-size;*returnColumnSizes result-columnSizes;return result-data;
}// 测试代码
int main() {int candidates[] {2, 3, 6, 7};int target 7;int returnSize;int* returnColumnSizes;int** result combinationSum(candidates, sizeof(candidates) / sizeof(candidates[0]), target, returnSize, returnColumnSizes);printf(组合总和的结果为\n);for (int i 0; i returnSize; i) {printf([);for (int j 0; j returnColumnSizes[i]; j) {printf(%d, result[i][j]);if (j returnColumnSizes[i] - 1) printf(, );}printf(]\n);free(result[i]);}free(result);free(returnColumnSizes);return 0;
}代码解析
1. 初始化结果数组
定义一个 ResultArray 结构体包含数据数组 data、列大小数组 columnSizes、当前大小 size 和容量 capacity。通过 createResultArray 函数初始化一个动态数组。
ResultArray* createResultArray() {ResultArray* result (ResultArray*)malloc(sizeof(ResultArray));result-data (int**)malloc(100 * sizeof(int*));result-columnSizes (int*)malloc(100 * sizeof(int));result-size 0;result-capacity 100;return result;
}2. 添加组合到结果数组
addResult 函数用于将找到的合法组合存储到结果数组中。如果容量不足使用 realloc 动态扩展容量。
void addResult(ResultArray* result, int* combination, int length) {if (result-size result-capacity) {result-capacity * 2;result-data (int**)realloc(result-data, result-capacity * sizeof(int*));result-columnSizes (int*)realloc(result-columnSizes, result-capacity * sizeof(int));}result-data[result-size] (int*)malloc(length * sizeof(int));for (int i 0; i length; i) {result-data[result-size][i] combination[i];}result-columnSizes[result-size] length;result-size;
}3. 回溯函数
backtrack 函数用于递归生成每一种可能的组合
如果 target 0说明找到了一个符合要求的组合调用 addResult。如果 target 0则组合无效直接返回。否则遍历从 start 开始的候选数字并递归调用 backtrack 函数。
void backtrack(int* candidates, int candidatesSize, int target, int* combination, int length, int start, ResultArray* result) {if (target 0) {addResult(result, combination, length);return;}if (target 0) return;for (int i start; i candidatesSize; i) {combination[length] candidates[i];backtrack(candidates, candidatesSize, target - candidates[i], combination, length 1, i, result);}
}4. 主函数
combinationSum 函数负责初始化组合数组 combination调用 backtrack 寻找所有组合设置返回结果的大小和列大小数组返回结果数组。
int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {ResultArray* result createResultArray();int* combination (int*)malloc(target * sizeof(int)); // 存储单个组合backtrack(candidates, candidatesSize, target, combination, 0, 0, result);*returnSize result-size;*returnColumnSizes result-columnSizes;return result-data;
}
