ZeroJudge 解題筆記：e446. 排列生成

作者：王一哲
日期：2025年9月22日 第二版：2026年9月10日，重寫 dfs 窮舉的程式碼


ZeroJudge 題目連結：e446. 排列生成

解題想法

這題不論用 Python 還是 C++ 都可以用遞迴窮舉所有的排列方式。在 Python 也可以用 itertools.permutaions，在 C++ 也可以用 next_permutation。但主要的困難之處是輸出速度，要加速才能過關。

2026年9月10日更新，重寫 dfs 窮舉的程式碼

Python，使用時間約為 8.6 s，記憶體約為 9.6 MB，通過測試。

def solve():
    import sys

    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1

        def dfs(path, visited):
            if len(path) == n:
                res = " ".join(map(str, path)) + "\n"
                sys.stdout.write(res)
                return
            
            for i in range(1, n+1):
                if visited[i]: continue
                visited[i] = True
                path.append(i)
                dfs(path, visited)
                visited[i] = False
                path.pop()
        # End of DFS
        dfs([], [False] * (n+1))

if __name__ == "__main__":
    solve()

C++，使用時間約為 2.9 s，記憶體約為 3.9 MB，通過測試。

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

int n;

void dfs(vector<int>& path, vector<bool>& visited) {
    if ((int)path.size() == n) {
        for(int i = 0; i < n; i++) {
            printf("%d", path[i]);
            if (i == n-1) printf("\n");
            else printf(" ");
        }
        return;
    }

    for(int i = 1; i <= n; i++) {
        if (visited[i]) continue;
        visited[i] = true;
        path.push_back(i);
        dfs(path, visited);
        visited[i] = false;
        path.pop_back();
    }
}

int main() {
    while(scanf("%d", &n) != EOF) {
        vector<int> path;
        vector<bool> visited (n+1, false);
        dfs(path, visited);
    }
    return 0;
}

Python 程式碼

窮舉，用 print 輸出，超時。

def solve(arr, n, used):
    if len(arr) == n:
        print(*arr)
        return
    for i in range(1, n+1):
        if i in used: continue
        used.add(i)
        arr.append(i)
        solve(arr, n, used)
        used.remove(i)
        arr.pop()
    return

solve([], int(input()), set())

窮舉，用 sys.stdout.write 輸出，超時。

import sys

def solve(arr, n, used):
    if len(arr) == n:
        s = " ".join(map(str, arr)) + "\n"
        sys.stdout.write(s)
        return
    for i in range(1, n+1):
        if i in used: continue
        used.add(i)
        arr.append(i)
        solve(arr, n, used)
        used.remove(i)
        arr.pop()
    return

solve([], int(sys.stdin.readline()), set())

用 itertools.permutations，用 sys.stdout.write 最後再一次輸出所有結果，最後一筆測資超出記憶體上限。

import sys, itertools

result = []
n = int(sys.stdin.readline())
nums = list(range(1, n+1))
for perm in itertools.permutations(nums):
    s = " ".join(map(str, perm))
    result.append(f"{s}\n")
sys.stdout.write("".join(result))

用 itertools.permutations，用 sys.stdout.write 逐行輸出結果。使用時間約為 12.3 s，記憶體約為 3.4 MB，通過測試。

import sys, itertools

n = int(sys.stdin.readline())
nums = list(range(1, n+1))
for perm in itertools.permutations(nums):
    s = " ".join(map(str, perm)) + "\n"
    sys.stdout.write(s)

C++ 程式碼

使用時間約為 9.3 s，記憶體約為 344 kB，通過測試。

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int N;
void perm(int depth, int maxDepth, vector<int>& nums, set<int>& tested) {
    if (depth == maxDepth) {
        for(int i=0; i<(int)nums.size(); i++)
            cout << nums[i] << " \n"[i == (int)nums.size()-1];
        return;
    }
    for(int i=1; i<=N; i++) {
        if (tested.count(i) == 1) continue;
        tested.insert(i);
        nums.push_back(i);
        perm(depth+1, maxDepth, nums, tested);
        tested.erase(i);
        nums.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    vector<int> nums;
    set<int> tested;
    perm(0, N, nums, tested);
    return 0;
}

使用時間約為 7.8 s，記憶體約為 352 kB，通過測試。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    int nums[N];
    for(int i=0; i<N; i++) {
        nums[i] = i+1;
        cout << i+1 << " \n"[i == N-1];
    }
    while(next_permutation(nums, nums+N)) {
        for(int i=0; i<N; i++)
            cout << nums[i] << " \n"[i == N-1];
    }
    return 0;
}