C++ 全排列遞歸算法深度解析：以空間換時間的經典回溯思想

核心思想

全排列的遞歸定義：設集合 R = {r₁, r₂, ..., rₙ}，Rᵢ = R - {rᵢ}。則 Perm(R) = (r₁) + Perm(R₁) ∪ (r₂) + Perm(R₂) ∪ ... ∪ (rₙ) + Perm(Rₙ)。基例 n=1 時 Perm(R) = (r)。

具體執行流程以 {1,2,3} 為例

第一層遞歸：固定第一位

• 交換位置 0 和 0 → {1,2,3} → 遞歸處理 {2,3}
• 交換位置 0 和 1 → {2,1,3} → 遞歸處理 {1,3}
• 交換位置 0 和 2 → {3,2,1} → 遞歸處理 {2,1}

第二層遞歸：固定第二位

以 {1,2,3} 為例，進入遞歸處理 {2,3}：

• 交換 0 和 0 → {2,3} → 輸出 1,2,3
• 交換 0 和 1 → {3,2} → 輸出 1,3,2
• 交換回 {2,3} 保持狀態

關鍵點：狀態恢復

每次交換後遞歸，返回時必須交換回原狀，確保同層後續迭代的正確性。這是回溯法的核心：做選擇 → 遞歸 → 撤銷選擇。

C++ 完整實現

#include 
using namespace std;

void swap(int &a, int &b) { int t = a; a = b; b = t; }

void perm(int list[], int low, int high) {
    if (low == high) {
        for (int i = 0; i <= high; i++) cout << list[i];
        cout << " ";
        return;
    }
    for (int i = low; i <= high; i++) {
        swap(list[low], list[i]);      // 做選擇
        perm(list, low + 1, high);     // 遞歸
        swap(list[low], list[i]);      // 撤銷選擇
    }
}

int main() {
    int a[] = {1, 2, 3};
    perm(a, 0, 2);
    return 0;
}
// 輸出：123 132 213 231 321 312

複雜度與優化

• 時間複雜度：O(n!)，輸出所有排列的理論下界。
• 空間複雜度：O(n)，遞歸棧深度。
• 可使用 std::next_permutation 實現非遞歸字典序生成。

總結

全排列遞歸是回溯法的教科書級範例。通過交換元素固定前綴、遞歸處理剩餘、回溯恢復狀態，優雅地解決了排列生成問題。理解其「選擇-遞歸-撤銷」三部曲，對掌握 DFS/回溯算法至關重要。