leetcode : Permutations

runtime 0 ms, beats 100% of cpp submissions
O(n x n!) solution with explanation

tags: backtracking

🔗 link

Permutations

📖 description

給定一個陣列，回傳他全部能組合的排列，陣列中不會有重複的元素。

ex.
    Input: nums = [1,2,3]

    Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

🧠 solution

所謂的全排列，其實就是把每個點都往後換看看，組成一個全新的排列，但在這裡會面對到一個問題，比如過程中可能出現重複的狀態，此時我們可以使用 set 來去除重複項，但這樣做會增加計算量以及空間的需求，所以我們可以透過讓操作出現順序性來避免，比如一定先從第 1 位往後換 (以此類推 2、3 …) ，以及交換只能往後換，這樣就不會出先交換 1、2 再交換 2、1 出現重複的狀態，也不會有交換 1、2 , 2、3 與 2、3 , 1、3 的情況。

還有一個最重要的重點，每次交換時我們可以選擇不換。

⏳ time complexity

共有 n! 個解，每個解都經過 n 次交換，時間複雜度 O(n x n!)
總時間複雜度 O(n x n!)

📝 code

class Solution {
public:
    vector<vector<int>> ans;
    void re(vector<int>& n,int ind){
        if(ind == n.size()){
            ans.emplace_back(n);
        }
        for(int i=ind;i<n.size();i++){  // 當 i=ind 時不會交換元素
            swap(n[ind],n[i]);
            re(n,ind+1);
            swap(n[ind],n[i]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        re(nums,0);
        return ans;
    }
};