人森很精彩，所以要把所有事情都記起來=ˇ=

繼上一題Combination Sum

馬上打鐵趁熱(?)，來看一題類似但有點不一樣的題目

給定一串不重複的數列，排出所有的排列組合

例如：

Input: [1,2,3]

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

Sol：

套用上一題的方式其實也可以解出來，大概是以下這樣：

    vector<int> m_nums;
    vector<vector<int>> m_viRet;
    
    void generatePermutation(vector<int> remainedNums, vector<int> permutation)
    {
        if (permutation.size() == m_nums.size())
        {
            m_viRet.push_back(permutation);
            return;
        }
        
        for (int i = 0; i < remainedNums.size(); ++i)
        {
            permutation.push_back(remainedNums[i]);
            
            int iTmp = remainedNums[i];
            remainedNums.erase(remainedNums.begin() + i);
            
            generatePermutation(remainedNums, permutation);
            
            remainedNums.insert(remainedNums.begin() + i, iTmp);
            permutation.pop_back();
        }            
    }
    

總之就是把排進permutation的數值從remainedNums刪掉，在繼續找下一個數值去牌這樣

這樣就可以找出答案了

我一開始就是這樣做，但其實可以有另一個思維，因為這個問題是在找排列組合

所以我看到網友有另一個方法覺得滿好的，他是用調換位置的方式去做：

    vector<vector<int>> m_viRet;
    
    void generatePermutation(vector<int>& nums, int begin)
    {   
        if (begin >= nums.size())
        {
            m_viRet.push_back(nums);
            return;            
        }
        
        for (int i = begin; i < nums.size(); ++i)
        {   
            swap(nums[begin], nums[i]);
            
            generatePermutation(nums, begin + 1);
            
            swap(nums[i], nums[begin]);
        }            
    }

嗯...，這個可以解釋一下嗎，為什麼這樣可以

以123的例子來看好了，流程是這樣：

123經過第一輪的調換之後，會得到123、213、321(第一個數字和後面數字交換位置，包含第一個數字自己，也就是沒有調換)

接著123、213、321會進行第二輪交換，也就是第二個數字要和後面的數字交換位置

在第二輪中123會得到123、132兩個組合，213會得到213、231，321會得到321、312

接著第三輪其實就不用交換了，因為數列長度就只有3，於是解就全部出來了

就是123、132、213、231、321、312這六個

至於你要說這是什麼原理...，我想也不是什麼原理，就是數學吧XD

其實很多很好的演算法都是要有很好的數學才能想出來的，然後能想出來是一回事，能實作出來又是一回事了

這些題目對我來說就是學習用遞迴來解決問題吧XD，順便看看網友們的各種厲害解法

那麼這題就這樣了~ 希望我打成網誌會比較有印象XD