Java 生成 0-9 十位數全排列：首位非零、無重複的遞歸回溯標準實現

問題需求

• 使用數字 0-9 生成所有十位數排列組合。
• 首位不能為 0。
• 每個數字不重複使用（全排列）。

算法分析

本質是長度為 10 的全排列，約束條件：perm[0] != '0'。總數為 9 × 9! = 3,265,920 個。採用遞歸回溯 + 交換法，時間複雜度 O(N!)，空間複雜度 O(N) (遞歸棧)。

標準實現代碼

public class PermutationGenerator {

    public static void main(String[] args) {
        String[] digits = {"0","1","2","3","4","5","6","7","8","9"};
        permute(digits, 0);
    }

    // 交換輔助函數
    private static void swap(String[] arr, int i, int j) {
        String tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 核心遞歸：從 start 位置開始固定，後續全排列
    private static void permute(String[] arr, int start) {
        if (start == arr.length - 1) {
            // 叶子節點：輸出一個完整排列
            // 首位非零檢查 (start=0 時已保證，此處兜底)
            if (!arr[0].equals("0")) {
                System.out.println(String.join("", arr));
            }
            return;
        }

        for (int i = start; i < arr.length; i++) {
            // 剪枝：首位 (start==0) 不能選 '0'
            if (start == 0 && arr[i].equals("0")) continue;

            swap(arr, start, i);          // 做選擇
            permute(arr, start + 1);      // 遞歸
            swap(arr, start, i);          // 撤銷選擇 (回溯)
        }
    }
}

關鍵點解析

1. 交換法原地排列：無需額外 visited 數組，空間優化。
2. 剪枝在循環層：start == 0 時跳過 '0'，避免生成無效排列再過濾，效率提升 10%。
3. 回溯恢復狀態：第二次 swap 還原數組，保證同層其他分支看到原始順序。

性能優化建議 (百萬級輸出)

• StringBuilder 批量輸出：避免頻繁 System.out.println 刷新緩衝區。

  StringBuilder sb = new StringBuilder();
          // 遞歸中 sb.append(...).append('\n');
          // 最後一次性 System.out.print(sb);

• 迭代器模式懶加載：實現 Iterator，按需生成，避免內存爆炸。
• 並行化：按首位數字 1-9 分桶，多線程並行生成 (需線程安全收集器)。

總結

十位數全排列首位非零，核心是交換法回溯 + 首層剪枝。代碼簡潔、邏輯清晰，配合 StringBuilder 批量輸出可高效處理 326 萬條數據。掌握此模板，可解決所有「固定長度、無重複、有約束」的排列組合問題。