算法題：字符串全排列生成（C語言遞歸交換法）

問題描述

輸入一個字符串，輸出其所有字符的全排列。如 abc 輸出 abc acb bac bca cba cab。

遞歸交換思路

1. 固定第 k 位字符，遞歸生成剩餘位置的排列。
2. 通過交換 str[k] 與 str[i] (i>=k) 實現固定不同字符。
3. 遞歸返回後交換回溯，恢復原序列供下一次迭代。

核心代碼

#include <stdio.h>

void Permutation(char* pStr, char* pBegin) {
    if (*pBegin == '\0') {
        printf("%s ", pStr);
    } else {
        for (char* pCh = pBegin; *pCh != '\0'; ++pCh) {
            char tmp = *pCh; *pCh = *pBegin; *pBegin = tmp; // 交換
            Permutation(pStr, pBegin + 1);
            tmp = *pCh; *pCh = *pBegin; *pBegin = tmp;     // 回溯
        }
    }
}

void Permutation(char* pStr) {
    if (pStr) Permutation(pStr, pStr);
}

int main(void) {
    char str[] = "abc";
    Permutation(str);
    putchar('\n');
    return 0;
}

輸出結果

abc acb bac bca cba cab

複雜度

• 時間：O(n × n!) —— n! 個排列，每個打印 O(n)。
• 空間：O(n) —— 遞歸棧深度。