LeetCode Permutations：全排列生成的回溯 + 交換法經典實現

題目大意

給定無重複元素數組 nums，返回所有全排列。例：[1,2,3] → 6 個排列。

回溯 + 交換法（原地生成）

遞歸函數 backtrack(first)：將 first 位置確定，通過交換 nums[first] 與 nums[i] (i ≥ first) 選擇當前位元素，遞歸處理 first+1，回溯時交換回原位。
終止條件：first == n，將當前 nums 加入結果。

C++ 實現

class Solution {
public:
    vector> permute(vector& nums) {
        vector> res;
        backtrack(nums, 0, res);
        return res;
    }
    void backtrack(vector& nums, int first, vector>& res) {
        if (first == nums.size()) {
            res.push_back(nums);
            return;
        }
        for (int i = first; i < nums.size(); ++i) {
            swap(nums[first], nums[i]);
            backtrack(nums, first + 1, res);
            swap(nums[first], nums[i]); // 回溯恢復
        }
    }
};

Java 實現

class Solution {
    public List> permute(int[] nums) {
        List> res = new ArrayList<>();
        backtrack(nums, 0, res);
        return res;
    }
    void backtrack(int[] nums, int first, List> res) {
        if (first == nums.length) {
            List perm = new ArrayList<>();
            for (int x : nums) perm.add(x);
            res.add(perm);
            return;
        }
        for (int i = first; i < nums.length; ++i) {
            swap(nums, first, i);
            backtrack(nums, first + 1, res);
            swap(nums, first, i);
        }
    }
    void swap(int[] a, int i, int j) { int t=a[i]; a[i]=a[j]; a[j]=t; }

Python 實現

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        def backtrack(first):
            if first == len(nums):
                res.append(nums[:])
                return
            for i in range(first, len(nums)):
                nums[first], nums[i] = nums[i], nums[first]
                backtrack(first + 1)
                nums[first], nums[i] = nums[i], nums[first]
        backtrack(0)
        return res

複雜度

• 時間：O(n × n!)，生成 n! 個排列，每個複製 O(n)。
• 空間：O(n) 遞歸棧 + O(n!) 結果存儲。

總結

LeetCode 46 是「全排列回溯」的教科書級題目。交換法 無需額外 used 數組，空間效率最高，代碼最簡潔。掌握此模板可秒殺 LeetCode 47（含重複元素全排列，加剪枝）、組合生成等變體。