题解 | 全排列

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

//定义全局变量
int *res = NULL;//存储结果准备打印的数组
int a_num = 0;//存储已经选择好的元素数量
int *flag = NULL;//用来标记是否已经取到i

//构建dfs回溯算法
void dfs(int n){
    //终止条件
    if(a_num == n){
        //打印一种排列
        for(int i = 0; i < n; i++){
            printf("%d ",res[i]);
        }
        printf("\n");//换行
        return;//返回
    }
    //遍历所有可能
    for(int i = 1; i <= n; i++){
        //加入结点并标记
        if(flag[i - 1] == 0){
            res[a_num] = i;
            flag[i - 1] = 1;
            a_num++;
            //递归
            dfs(n);
            //撤销选择
            a_num --;
            flag[i - 1] = 0;
        }
    }
}

int main() {
    //读取数据
    int n;
    scanf("%d\n", &n);
    
    //为res和flag分配空间并赋初值
    res = (int *)malloc(sizeof(int) * n);
    flag = (int *)malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++){
        res[i] = 0;
        flag[i] = 0;
    }
    //调用深度优先搜索
    dfs(n);
    
    //释放空间
    free(res);
    free(flag);
    return 0;
}