C语言排列组合算法详解（从零开始掌握排列与组合的编程实现）

一、C语言实现全排列（递归法）

全排列是最常见的排列问题，即对一个数组的所有元素进行重新排序。我们可以使用递归 + 回溯的方法来实现。

代码实现：

#include <stdio.h>#include <string.h>// 交换两个整数void swap(int *a, int *b) {    int temp = *a;    *a = *b;    *b = temp;}// 递归生成全排列void permute(int arr[], int start, int end) {    if (start == end) {        // 打印当前排列        for (int i = 0; i <= end; i++) {            printf("%d ", arr[i]);        }        printf("\n");        return;    }    for (int i = start; i <= end; i++) {        swap(&arr[start], &arr[i]);      // 交换        permute(arr, start + 1, end);     // 递归        swap(&arr[start], &arr[i]);      // 回溯（恢复原状）    }}int main() {    int arr[] = {1, 2, 3};    int n = sizeof(arr) / sizeof(arr[0]);    printf("全排列结果：\n");    permute(arr, 0, n - 1);    return 0;}

这段代码展示了经典的“C语言全排列”实现方式。核心思想是：固定第一个位置，递归处理后面的部分，每一步完成后通过回溯恢复数组状态，确保下一次尝试不受影响。

二、C语言实现组合（从n个中选k个）

组合问题通常使用递归或位运算解决。这里我们采用递归方法，逐个决定是否选择当前元素。

代码实现：

#include <stdio.h>// 打印当前组合void printCombination(int data[], int k) {    for (int i = 0; i < k; i++) {        printf("%d ", data[i]);    }    printf("\n");}// 递归生成组合void combinationUtil(int arr[], int data[], int start, int end,                    int index, int r) {    // 如果已选够 r 个元素    if (index == r) {        printCombination(data, r);        return;    }    // 从 start 到 end 遍历剩余元素    for (int i = start; i <= end && end - i + 1 >= r - index; i++) {        data[index] = arr[i];        combinationUtil(arr, data, i + 1, end, index + 1, r);    }}void printCombinationMain(int arr[], int n, int r) {    int data[r];    combinationUtil(arr, data, 0, n - 1, 0, r);}int main() {    int arr[] = {1, 2, 3, 4};    int r = 2;    int n = sizeof(arr) / sizeof(arr[0]);    printf("从 %d 个数中选 %d 个的组合：\n", n, r);    printCombinationMain(arr, n, r);    return 0;}

上述代码实现了C语言组合算法，能从 n 个元素中选出 k 个所有可能的组合。关键在于控制递归深度（index）和起始位置（start），避免重复选择。

三、常见应用场景

掌握排列组合递归实现后，你可以应用于以下场景：

• 密码暴力破解（生成所有可能的字符排列）
• 数学竞赛题（如求所有子集、路径问题）
• 算法面试题（如 LeetCode 的 Permutations、Combinations 系列）
• 游戏开发中的随机事件组合生成

总结

通过本文，你已经学会了如何用 C 语言实现排列与组合的基本算法。核心技巧是递归 + 回溯，这是解决此类问题的通用思路。建议你动手敲一遍代码，加深理解。随着练习增多，你会越来越熟练地运用这些C语言排列组合算法解决实际问题！

提示：在实际项目中，若数据量较大，可考虑使用迭代法或优化剪枝策略以提升性能。