题解 | 全排列

#include <stdio.h>

int n;
int path[10];      // 当前排列
int used[10];      // 标记数字是否已使用

// DFS生成排列
void dfs(int u) {
    // 终止条件：填满了n个数
    if (u == n) {
        for (int i = 0; i < n; i++) {
            printf("%d", path[i]);
            if (i < n - 1) printf(" ");
        }
        printf("\n");
        return;
    }
    
    // 按顺序尝试 1~n
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {           // 如果数字i还没用过
            path[u] = i;          // 填入当前位置
            used[i] = 1;          // 标记为已使用
            
            dfs(u + 1);           // 填下一个位置
            
            used[i] = 0;          // 回溯：恢复状态******************************************
        }
    }
}

int main() {
    scanf("%d", &n);
    dfs(0);  // 从第0个位置开始填
    return 0;
}