Java 字符數組全排列算法實現（遞歸回溯法）

問題描述

給定一個字符數組（如 {'a','b','c'}），輸出其所有可能的排列組合。本文採用經典的遞歸回溯算法，通過交換元素位置實現全排列。

核心算法邏輯

public void permutation(char[] buf, int start, int end) {
    if (start == end) {
        // 遞歸終止條件：輸出當前排列
        for (int i = 0; i <= end; i++) System.out.print(buf[i]);
        System.out.println();
    } else {
        for (int i = start; i <= end; i++) {
            // 交換：將第 i 個元素移到 start 位置
            swap(buf, start, i);
            // 遞歸處理剩餘子數組
            permutation(buf, start + 1, end);
            // 回溯：恢復原順序，供下一次迭代使用
            swap(buf, start, i);
        }
    }
}

private void swap(char[] buf, int i, int j) {
    char temp = buf[i];
    buf[i] = buf[j];
    buf[j] = temp;
}

執行流程以 {a,b,c} 為例

1. 首輪固定 a，遞歸處理 {b,c} → 輸出 abc, acb
2. 交換 a 與 b，固定 b，遞歸處理 {a,c} → 輸出 bac, bca
3. 交換 a 與 c，固定 c，遞歸處理 {b,a} → 輸出 cba, cab

測試輸出

abc
acb
bac
bca
cba
cab

複雜度分析

• 時間複雜度：O(n × n!) —— 需生成 n! 個排列，每個排列輸出需 O(n)。
• 空間複雜度：O(n) —— 遞歸棧深度為 n，原地交換無額外空間。

應用場景

全排列算法常用於組合優化問題（如旅行商問題）、密碼暴力破解、遊戲 AI 搜索等場景。理解其回溯思想對掌握遞歸算法至關重要。