搜索算法入門：全排列生成與格式控制的踩坑記錄

題目背景

給定 4 個不同數字，生成所有不重複的 4 位排列，每行輸出一組，組間空行分隔測試用例。

回溯框架

void dfs(int pos) {
    if (pos == 4) { output(); return; }
    for (int d=0; d<10; d++) if (avail[d]) {
        avail[d] = 0; path[pos] = d;
        dfs(pos+1);
        avail[d] = 1;
    }
}

格式控制關鍵

• 每組輸出後換行。
• 測試用例間輸出空行（首個用例前不輸出）。
• 使用全局標記 first_case 控制。

完整代碼

#include <stdio.h>
#include <string.h>

int avail[10], path[4];
int first_case = 1;

void output() {
    if (!first_case) printf("\n");
    first_case = 0;
    for (int i=0; i<4; i++) printf("%d", path[i]);
    printf("\n");
}

void dfs(int pos) {
    if (pos == 4) { output(); return; }
    for (int d=0; d<10; d++) if (avail[d]) {
        avail[d]=0; path[pos]=d;
        dfs(pos+1);
        avail[d]=1;
    }
}

int main() {
    int a,b,c,d;
    while (scanf("%d%d%d%d",&a,&b,&c,&d)==4) {
        if (a==0&&b==0&&c==0&&d==0) break;
        memset(avail,0,sizeof(avail));
        avail[a]=avail[b]=avail[c]=avail[d]=1;
        dfs(0);
    }
    return 0;
}

心得

• 搜索題核心：狀態定義、遞歸邊界、狀態恢復。
• 格式細節最易丟分，需嚴格對照題目輸出範例。
• 獨立完成第一道搜索題，建立信心。