全排列問題完全攻略：字典序輸出、去重與遞歸回溯實戰

問題定義

給定一個可能包含重複字元的字串 (以逗號結尾)，要求按字典序、不重複輸出所有全排列。

• 輸入 abc, → 輸出 abc acb bac bca cab cba
• 輸入 cab, → 輸出 abc acb bac bca cab cba (先排序)
• 輸入 abb, → 輸出 abb bab bba (去重)

核心思路：排序 + 遞歸回溯 + 去重剪枝

1. 預排序：將輸入字串轉為字元陣列並 qsort 升序，保證遞歸生成順序天然為字典序。
2. 遞歸框架：permute(pos) 固定前 pos 位，對剩餘位全排列。
   • 終止條件：pos == len，輸出當前排列。
   • 遞歸步驟：對 i = pos .. len-1，交換 a[pos] ↔ a[i]，遞歸 permute(pos+1)，回溯交換回來。
3. 去重關鍵：在交換前檢查 [pos, i-1] 區間是否已存在 a[i]。若存在，說明該字元在當前位置已被嘗試過，直接 continue 跳過，避免生成重複排列。因陣列有序，重複字元相鄰，檢查高效。

完整 C 實現 (含註釋)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(char *a, char *b) { char t = *a; *a = *b; *b = t; }

// 檢查 [start, end) 區間是否已存在字元 c
int is_duplicate(char *s, int start, int end, char c) {
    for (int i = start; i < end; ++i)
        if (s[i] == c) return 1;
    return 0;
}

void permute(char *s, int pos, int len) {
    if (pos == len) {
        printf("%s ", s);
        return;
    }
    for (int i = pos; i < len; ++i) {
        if (is_duplicate(s, pos, i, s[i])) continue;  // 去重剪枝
        swap(&s[pos], &s[i]);
        permute(s, pos + 1, len);
        swap(&s[pos], &s[i]);  // 回溯恢復
    }
}

int main() {
    char input[100], *p;
    if (!fgets(input, sizeof(input), stdin)) return 0;
    if ((p = strchr(input, ',')) != NULL) *p = '\0';  // 截取逗號前內容
    int len = strlen(input);
    qsort(input, len, 1, (int(*)(const void*,const void*))strcmp);  // 字典序預排序
    permute(input, 0, len);
    printf("\n");
    return 0;
}

遞歸調用狀態圖解 (以 abc 為例)

permute(pos=0)
 ├─ i=0: swap(a,a) → "abc" → permute(1)
 │    ├─ i=1: swap(b,b) → "abc" → permute(2) → 輸出 "abc"
 │    └─ i=2: swap(b,c) → "acb" → permute(2) → 輸出 "acb"
 ├─ i=1: swap(a,b) → "bac" → permute(1)
 │    ├─ i=1: swap(a,a) → "bac" → permute(2) → 輸出 "bac"
 │    └─ i=2: swap(a,c) → "bca" → permute(2) → 輸出 "bca"
 └─ i=2: swap(a,c) → "cba" → permute(1)
      ├─ i=1: swap(b,b) → "cba" → permute(2) → 輸出 "cba"
      └─ i=2: swap(b,a) → "cab" → permute(2) → 輸出 "cab"

每層 for 迴圈遍歷「當前位可選字元」，遞歸處理「剩餘位全排列」，回溯交換恢復現場，保證下一輪迭代基於原始有序狀態。

複雜度分析

• 時間：O(n! × n) — n! 個排列，每個輸出/交換 O(n)。去重不改變最坏情況階乘級上界。
• 空間：O(n) — 遞歸棧深度 + 原地交換無額外空間。

常見變體擴展

• LeetCode 46. Permutations：無重複元素，同上框架去重邏輯可省略。
• LeetCode 47. Permutations II：含重複元素，本文去重邏輯直接適用。
• 下一個排列：非遞歸、原地修改生成字典序下一排列 (STL next_permutation 算法)，O(n) 時間 O(1) 空間。

總結

全排列是回溯算法的「Hello World」。掌握 排序去重 + 交換回溯 + 原地修改 三板斧，即可應對所有排列類問題。關鍵細節：is_duplicate 利用有序性將去重降為 O(n) 掃描，避免 set 額外空間與常數開銷。