全排列生成算法：從固定 N 到任意 N 的遞歸回溯實現

問題演進

• 固定 4 數：四層巢狀循環，代碼冗長、不可擴展。
• 任意 N 數：必須用遞歸回溯，將「選下一個數」抽象為統一邏輯。

回溯核心框架

void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {
    if (path.size() == nums.size()) {
        res.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;
        used[i] = true;
        path.push_back(nums[i]);
        backtrack(nums, used, path, res);
        path.pop_back();
        used[i] = false;
    }
}

完整 C++ 程序

#include <bits/stdc++.h>
using namespace std;

void permute(const vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {
    if (path.size() == nums.size()) {
        res.push_back(path);
        return;
    }
    for (int i = 0; i < (int)nums.size(); i++) {
        if (used[i]) continue;
        used[i] = true;
        path.push_back(nums[i]);
        permute(nums, used, path, res);
        path.pop_back();
        used[i] = false;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; 
    if (!(cin >> n)) return 0;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    vector<bool> used(n, false);
    vector<int> path;
    vector<vector<int>> res;
    permute(nums, used, path, res);
    for (auto& p : res) {
        for (int i = 0; i < (int)p.size(); i++) {
            if (i) cout << ' ';
            cout << p[i];
        }
        cout << '\n';
    }
    return 0;
}

輸入輸出示例

輸入：
3
1 2 3

輸出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

複雜度分析

註：輸出本身即需 O(n! × n) 時間，算法已達理論最優。

進階優化：字典序生成 (STL next_permutation)

vector<int> a = nums;
sort(a.begin(), a.end());
do {
    // 處理 a
} while (next_permutation(a.begin(), a.end()));

• 自動按字典序生成，無需 used 數組。
• 原地修改，空間 O(1) 額外空間。
• C++ STL 標準庫實現，工程首選。

去重全排列（含重複元素）

排序後，在回溯循環中添加剪枝：

if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;

確保相同數值只在第一次未使用時被選取，避免重複排列。

總結

全排列是回溯算法的入門範本。掌握「路徑、選擇列表、終止條件」三要素，即可推導出組合、子集、N 皇后等所有回溯問題。工程中優先用 next_permutation，面試手寫回溯框架需熟練到「閉眼能寫」。