POJ 1731 Orders：全排列去重與 next_permutation

問題描述

給定字符串，輸出其所有不重複的全排列，按字典序排列。字符串可能包含重複字符。

解法：STL next_permutation

next_permutation 會自動處理重複元素，生成嚴格遞增的字典序排列。只需先 sort，然後 do { ... } while (next_permutation(...))。

參考代碼框架（C++）

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

char str[205];
int main() {
    while (cin >> str) {
        int len = strlen(str);
        sort(str, str + len);
        do {
            cout << str << endl;
        } while (next_permutation(str, str + len));
    }
    return 0;
}

手寫全排列去重（DFS + 剪枝）

若不使用 STL，需在 DFS 中跳過同層重複字符：

• 排序字符數組
• 遞歸時，若 i > 0 && a[i] == a[i-1] && !used[i-1] 則 continue（關鍵剪枝）

複雜度

• 輸出敏感：O(k * n)，k 為不重複排列數
• STL 版本代碼最簡潔，推薦比賽使用