作者：王一哲
日期：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)
