C语言求组合数

### C语言实现组合数计算的方法 在C语言中，可以通过多种方式实现组合数的计算。以下提供一种基于递归和阶乘的方式实现组合数计算的代码示例[^1]。 ```c #include <stdio.h> // 计算阶乘的函数 long long factorial(int n) { if (n == 0 || n == 1) { return 1; } return n * factorial(n - 1); } // 计算组合数的函数 long long combination(int n, int r) { if (r > n) { return 0; } return factorial(n) / (factorial(r) * factorial(n - r)); } int main() { int n, r; printf("请输入n和r的值："); scanf("%d %d", &n, &r); long long result = combination(n, r); printf("C(%d, %d) = %lld\n", n, r, result); return 0; } ``` 此代码通过定义一个计算阶乘的函数 `factorial` 和一个计算组合数的函数 `combination` 来完成任务。用户输入 `n` 和 `r` 的值后，程序将输出对应的组合数结果[^1]。 此外，还可以使用回溯法来求解组合数的问题。这种方法尤其适用于需要枚举所有可能组合的情况。例如，可以参考以下代码示例[^2]： ```c #include <stdio.h> #include <stdlib.h> void backtrack(int* nums, int numsSize, int target, int* path, int pathSize, int start, int** result, int* returnSize, int** returnColumnSizes) { if (target == 0) { result[*returnSize] = (int*)malloc(sizeof(int) * pathSize); for (int i = 0; i < pathSize; i++) { result[*returnSize][i] = path[i]; } (*returnColumnSizes)[*returnSize] = pathSize; (*returnSize)++; return; } for (int i = start; i < numsSize && target >= nums[i]; i++) { path[pathSize] = nums[i]; backtrack(nums, numsSize, target - nums[i], path, pathSize + 1, i, result, returnSize, returnColumnSizes); } } int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) { *returnSize = 0; *returnColumnSizes = (int*)malloc(sizeof(int) * 100); int** result = (int**)malloc(sizeof(int*) * 100); int path[100]; // 对数组进行排序 for (int i = 0; i < candidatesSize - 1; i++) { for (int j = i + 1; j < candidatesSize; j++) { if (candidates[i] > candidates[j]) { int temp = candidates[i]; candidates[i] = candidates[j]; candidates[j] = temp; } } } backtrack(candidates, candidatesSize, target, path, 0, 0, result, returnSize, returnColumnSizes); return result; } int main() { int candidates[] = {2, 3, 6, 7}; int target = 7; int candidatesSize = sizeof(candidates) / sizeof(candidates[0]); int returnSize = 0; int* returnColumnSizes; int** result = combinationSum(candidates, candidatesSize, target, &returnSize, &returnColumnSizes); for (int i = 0; i < returnSize; i++) { for (int j = 0; j < returnColumnSizes[i]; j++) { printf("%d ", result[i][j]); } printf("\n"); } return 0; } ``` 上述代码展示了如何使用回溯法求解组合总和问题。通过递归地尝试每个候选值，程序可以找到所有满足条件的组合[^2]。