LeetCode-Day86(C++) 46. 全排列

1. 全排列

   給定一個不含重複數字的數組 nums ，傳回其 所有可能的全排列 。你可以 按任意順序 傳回答案。

示例 1：

輸入：nums = [1,2,3]

輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

輸入：nums = [0,1]

輸出：[[0,1],[1,0]]

示例 3：

輸入：nums = [1]

輸出：[[1]]

提示：

1 <= nums.length <= 6

-10 <= nums[i] <= 10

nums 中的所有整數 互不相同

方法一：回溯

思路和算法

這個問題可以看作有 n 個排列成一行的空格，我們需要從左往右依此填入題目給定的 n 個數，每個數隻能使用一次。那麼很直接的可以想到一種窮舉的算法，即從左往右每一個位置都依此嘗試填入一個數，看能不能填完這 nn 個空格，在程式中我們可以用「回溯法」來模拟這個過程。

我們定義遞歸函數 backtrack(first, output) 表示從左往右填到第 first 個位置，目前排列為 output。 那麼整個遞歸函數分為兩個情況：

如果first==n，說明我們已經填完了 n 個位置（注意下标從 0 開始），找到了一個可行的解，我們将output 放入答案數組中，遞歸結束。

如果first<n，我們要考慮這第first 個位置我們要填哪個數。根據題目要求我們肯定不能填已經填過的數，是以很容易想到的一個處理手段是我們定義一個标記數組vis[] 來标記已經填過的數，那麼在填第 first 個數的時候我們周遊題目給定的 n 個數，如果這個數沒有被标記過，我們就嘗試填入，并将其标記，繼續嘗試填下一個位置，即調用函數 backtrack(first + 1, output)。回溯的時候要撤銷這一個位置填的數以及标記，并繼續嘗試其他沒被标記過的數。

使用标記數組來處理填過的數是一個很直覺的思路，但是可不可以去掉這個标記數組呢？畢竟标記數組也增加了我們算法的空間複雜度。

答案是可以的，我們可以将題目給定的 n 個數的數組 nums 劃分成左右兩個部分，左邊的表示已經填過的數，右邊表示待填的數，我們在回溯的時候隻要動态維護這個數組即可。

具體來說，假設我們已經填到第 first 個位置，那麼nums 數組中 [0,first−1] 是已填過的數的集合，[first,n−1] 是待填的數的集合。我們肯定是嘗試用 [first,n−1] 裡的數去填第first 個數，假設待填的數的下标為 i ，那麼填完以後我們将第 i 個數和第 first 個數交換，即能使得在填第 first+1個數的時候 nums 數組的[0,first] 部分為已填過的數，[first+1,n−1] 為待填的數，回溯的時候交換回來即能完成撤銷操作。

舉個簡單的例子，假設我們有 [2, 5, 8, 9, 10] 這 5 個數要填入，已經填到第 3 個位置，已經填了 [8,9] 兩個數，那麼這個數組目前為 [8, 9 | 2, 5, 10] 這樣的狀态，分隔符區分了左右兩個部分。假設這個位置我們要填 10 這個數，為了維護數組，我們将 2 和 10 交換，即能使得數組繼續保持分隔符左邊的數已經填過，右邊的待填 [8, 9, 10 | 2, 5] 。

當然善于思考的讀者肯定已經發現這樣生成的全排列并不是按字典序存儲在答案數組中的，如果題目要求按字典序輸出，那麼請還是用标記數組或者其他方法。

class Solution {
public:
    void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
        // 所有數都填完了
        if (first == len) {
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; ++i) {
            // 動态維護數組
            swap(output[i], output[first]);
            // 繼續遞歸填下一個數
            backtrack(res, output, first + 1, len);
            // 撤銷操作
            swap(output[i], output[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};
           

複雜度分析

時間複雜度：O(n×n!)，其中 n 為序列的長度。

算法的複雜度首先受 backtrack 的調用次數制約

而對于 backtrack 調用的每個葉結點（共 n! 個），我們需要将目前答案使用O(n) 的時間複制到答案數組中，相乘得時間複雜度為 O(n×n!)。

是以時間複雜度為 O(n×n!)。

空間複雜度：O(n)，其中 n 為序列的長度。除答案數組以外，遞歸函數在遞歸過程中需要為每一層遞歸函數配置設定棧空間，是以這裡需要額外的空間且該空間取決于遞歸的深度，這裡可知遞歸調用深度為 O(n)。

作者：LeetCode-Solution

連結：https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/