C++ 遞迴計算全排列組合數

演算法思路

對 n 個元素求全排列：固定第 1 個位置，遞迴求剩餘 n-1 個元素的全排列，合併結果。基底情況：剩餘 1 個元素直接回傳。

步驟

1. 移除任意位置的一個元素，產生子序列。
2. 遞迴呼叫自身處理子序列。
3. 將移除的元素前綴加到每個子排列前，收集結果。

程式碼架構（略）

void permute(vector<int>& nums, int start, vector<vector<int>>& result) {
    if (start == nums.size()) { result.push_back(nums); return; }
    for (int i = start; i < nums.size(); ++i) {
        swap(nums[start], nums[i]);
        permute(nums, start + 1, result);
        swap(nums[start], nums[i]); // backtrack
    }
}

複雜度

• 時間：O(n! * n)
• 空間：O(n!) 儲存結果 + O(n) 遞迴堆疊

應用

• 組合優化問題（旅行推銷員、排程）。
• 測試用例生成、密碼暴力枚舉（小規模）。