字符串全排列：DFS 遞歸生成字典序排列

問題描述

給定由不同小寫字母組成、已按字典序排序的字符串（長度 1~6），輸出其所有全排列，按字典序升序，每行一個。

算法：DFS + 訪問標記

因輸入已有序，按順序選擇未用字符即可自然生成字典序排列。
狀態：path 當前排列，used[i] 字符是否已用。
遞歸：
- 若 path.size() == n，輸出。
- 否則對 i=0..n-1，若未用，標記、加入、遞歸、回溯。

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
string s;
bool used[7];
void dfs(string& path) {
    if (path.size() == s.size()) {
        cout << path << '\n';
        return;
    }
    for (int i = 0; i < s.size(); ++i) {
        if (!used[i]) {
            used[i] = true;
            path.push_back(s[i]);
            dfs(path);
            path.pop_back();
            used[i] = false;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> s) {
        fill(used, used + s.size(), false);
        string path;
        dfs(path);
        cout << '\n'; // 每組樣例結束額外換行
    }
    return 0;
}

複雜度

• 時間：O(n! × n)，n ≤ 6，最多 720 × 6 = 4320 操作。
• 空間：O(n) 遞歸棧 + path。

關鍵點

• 輸入已保證字符不同且有序，DFS 選擇順序即生成字典序。
• 回溯標準模板：選擇 → 遞歸 → 撤銷選擇。
• 每組輸出結束額外換行（題目要求）。

這是全排列生成的教科書級遞歸解法，簡潔高效，適用於小規模排列枚舉。