以下是用C语言实现数组全排列的回溯算法代码：

全排列生成算法实现

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

// 交换两个整数的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 深拷贝当前排列到结果集
void savePermutation(int* nums, int numsSize, int** result, int* returnSize) {
    result[*returnSize] = (int*)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        result[*returnSize][i] = nums[i];
    }
    (*returnSize)++;
}

// 回溯核心函数
void backtrack(int* nums, int numsSize, int start, int** result, int* returnSize) {
    if (start == numsSize) {  // 终止条件：生成完整排列
        savePermutation(nums, numsSize, result, returnSize);
        return;
    }
    
    for (int i = start; i < numsSize; i++) {
        swap(&nums[start], &nums[i]);    // 做选择：交换元素
        backtrack(nums, numsSize, start + 1, result, returnSize);  // 递归下一层
        swap(&nums[start], &nums[i]);    // 撤销选择：恢复状态
    }
}

// 主接口函数
int** permute(int* nums, int numsSize, int* returnSize) {
    // 计算排列总数 n!
    *returnSize = 1;
    for (int i = 1; i <= numsSize; i++) {
        *returnSize *= i;
    }
    
    // 分配结果内存
    int** result = (int**)malloc((*returnSize) * sizeof(int*));
    
    // 执行回溯算法
    *returnSize = 0;  // 重置为实际计数
    backtrack(nums, numsSize, 0, result, returnSize);
    
    return result;
}

// 打印结果
void printResult(int** result, int size, int numsSize) {
    for (int i = 0; i < size; i++) {
        printf("[");
        for (int j = 0; j < numsSize; j++) {
            printf("%d%s", result[i][j], (j < numsSize-1) ? ", " : "");
        }
        printf("]\n");
    }
}

// 示例使用
int main() {
    int nums[] = {1, 2, 3};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int returnSize;
    
    int** permutations = permute(nums, numsSize, &returnSize);
    
    printf("输入数组: [1, 2, 3]\n");
    printf("全排列结果(%d种):\n", returnSize);
    printResult(permutations, returnSize, numsSize);
    
    // 释放内存
    for (int i = 0; i < returnSize; i++) {
        free(permutations[i]);
    }
    free(permutations);
    
    return 0;
}

代码详细解析

1. 核心数据结构

int** result;  // 二维数组存储所有排列

• result 是指针数组，每个元素指向一个排列（一维数组）
• 内存布局示例（输入[1,2,3]）：

result[0] → [1,2,3]
result[1] → [1,3,2]
result[2] → [2,1,3]
...

2. 关键函数解析

swap() 函数

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

• 作用：交换两个整数的值
• 必要性：通过交换元素位置生成不同排列

savePermutation() 函数

void savePermutation(int* nums, int numsSize, int** result, int* returnSize) {
    result[*returnSize] = (int*)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        result[*returnSize][i] = nums[i];
    }
    (*returnSize)++;
}

• 深拷贝：将当前排列状态复制到结果集
• 内存管理：为每个排列单独分配内存
• 索引控制：通过returnSize参数跟踪存储位置

backtrack() 函数

void backtrack(int* nums, int numsSize, int start, int** result, int* returnSize) {
    if (start == numsSize) {  // 终止条件
        savePermutation(nums, numsSize, result, returnSize);
        return;
    }
    
    for (int i = start; i < numsSize; i++) {
        swap(&nums[start], &nums[i]);    // 做选择
        backtrack(nums, numsSize, start + 1, result, returnSize);  // 递归
        swap(&nums[start], &nums[i]);    // 撤销选择
    }
}

• 递归过程：
• 终止条件：当start == numsSize时，说明已处理完所有元素
• 循环遍历：从当前位置start开始，依次与后续元素交换
• 状态修改：通过交换生成新的排列
• 递归深入：处理下一个位置（start+1）
• 状态恢复：撤销交换以尝试其他可能性

permute() 函数

int** permute(int* nums, int numsSize, int* returnSize) {
    // 计算排列总数 n!
    *returnSize = 1;
    for (int i = 1; i <= numsSize; i++) {
        *returnSize *= i;
    }
    
    // 分配结果内存
    int** result = (int**)malloc((*returnSize) * sizeof(int*));
    
    // 执行回溯算法
    *returnSize = 0;  // 重置为实际计数
    backtrack(nums, numsSize, 0, result, returnSize);
    
    return result;
}

• 内存预分配：根据n!预先分配结果数组空间
• 双重角色：returnSize既用于返回结果数量，也用于控制存储位置

3. 算法执行流程

以输入数组[1,2,3]为例：

1. 初始调用 backtrack(0)
2. 第一层循环（start=0）
   - i=0: 交换位置0与0（无变化）
     → 递归进入 backtrack(1)
     → 第二层循环（start=1）
        - i=1: 交换位置1与1
          → 递归进入 backtrack(2)
          → 第三层循环（start=2）
             - i=2: 交换位置2与2
               → 触发终止条件，保存[1,2,3]
        - i=2: 交换位置1与2 → [1,3,2]
          → 递归处理生成排列
   - i=1: 交换位置0与1 → [2,1,3]
     → 递归处理生成排列
   - i=2: 交换位置0与2 → [3,2,1]
     → 递归处理生成排列

4. 复杂度分析

• 时间复杂度：O(n*n!)
• 生成n!种排列
• 每次保存排列需要O(n)时间
• 空间复杂度：O(n!)
• 存储所有排列需要n!×n的空间
• 递归栈深度为O(n)

5. 关键优化点

1. 原地交换：直接修改原数组，避免额外空间
2. 即时保存：只在完整排列时进行深拷贝
3. 预分配内存：提前计算所需空间，避免动态扩容

6. 内存管理示意图

permutations → [ ptr1, ptr2, ptr3, ... ]
                           ↗       ↗       ↗
                     [1,2,3] [1,3,2] [2,1,3] ...

扩展改进方向

1. 处理重复元素：添加跳过重复值的判断

if (i > start && nums[i] == nums[start]) continue;

2. 迭代实现：用栈模拟递归，避免栈溢出
3. 分块存储：对于大规模数据，使用分批生成和存储

通过这个实现，可以清晰看到回溯算法在排列生成中的应用，以及C语言中动态内存管理的具体实践。