HDU 1716 全排列輸出：DFS 遞歸與 STL next_permutation 兩種解法

題目大意

給定 4 張卡片（數字 0-9），用這 4 個數字組成所有不重複的 4 位數（千位不能為 0），按從小到大輸出。千位相同的同行，數字間空格分隔，測資之間空一行。

解法一：DFS 遞歸生成 + 排序去重

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int a[4], vis[4], ans[25], cnt, cur;

void dfs(int depth) {
    if (depth == 4) {
        if (cur >= 1000) ans[cnt++] = cur;
        return;
    }
    for (int i = 0; i < 4; i++) if (!vis[i]) {
        vis[i] = 1;
        cur = cur * 10 + a[i];
        dfs(depth + 1);
        cur = (cur - a[i]) / 10;
        vis[i] = 0;
    }
}

int main() {
    int first = 1;
    while (scanf("%d%d%d%d", &a[0], &a[1], &a[2], &a[3]) == 4) {
        if (a[0]==0 && a[1]==0 && a[2]==0 && a[3]==0) break;
        sort(a, a+4);
        if (!first) puts(""); else first = 0;
        memset(vis, 0, sizeof(vis));
        cnt = cur = 0;
        dfs(0);
        sort(ans, ans + cnt);
        int thousand = ans[0] / 1000;
        printf("%d", ans[0]);
        for (int i = 1; i < cnt; i++) {
            if (ans[i] == ans[i-1]) continue;          // 去重
            if (ans[i] / 1000 != thousand) {           // 換行
                printf("\n%d", ans[i]);
                thousand = ans[i] / 1000;
            } else {
                printf(" %d", ans[i]);
            }
        }
        puts("");
    }
    return 0;
}

解法二：STL next_permutation 一行搞定

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int a[4], first = 1;
    while (scanf("%d%d%d%d", &a[0], &a[1], &a[2], &a[3]) == 4) {
        if (a[0]==0 && a[1]==0 && a[2]==0 && a[3]==0) break;
        sort(a, a+4);
        if (!first) puts(""); else first = 0;
        int thousand = -1, printed = 0;
        do {
            if (a[0] == 0) continue;                 // 千位不能為 0
            if (!printed) { printf("%d%d%d%d", a[0],a[1],a[2],a[3]); printed = 1; }
            else if (a[0] == thousand) printf(" %d%d%d%d", a[0],a[1],a[2],a[3]);
            else { printf("\n%d%d%d%d", a[0],a[1],a[2],a[3]); thousand = a[0]; }
        } while (next_permutation(a, a+4));
        puts("");
    }
    return 0;
}

核心差異