LeetCode:Permutations(求全排列)

Given a collection of numbers, return all possible permutations.

For example,

<code>[1,2,3]</code> have the following permutations:

<code>[1,2,3]</code>, <code>[1,3,2]</code>, <code>[2,1,3]</code>, <code>[2,3,1]</code>, <code>[3,1,2]</code>, and <code>[3,2,1]</code>.

思路：将元素一個一個的插入，首先隻有一個元素{1}，此時，插入之後會的到兩個vector&lt;int&gt;，{1,2}，{2,1}，然後繼續插入第三個元素3，會得到{3,1,2}，{1,3,2}，{1,2,3}和{3,2,1}，{2,3,1}，{2,1,3}。

依次類推，将所有的元素插入其中。

C++代碼實作：

運作結果：

方法二，使用回溯的方法。

 方法三：利用遞歸的方法(遞歸-恢複-遞歸-恢複)

首先解釋下全排列怎麼生成的，看懂後代碼就好寫了。例如123，有6種排列方式，這其中有個規律，用第一個數字從前往後與所有數字交換(包括第一個數字本身)，每次交換都确定一個位置。

123——最左邊的數字确定了——中間的數字确定了

|——123(交換1與1所得)——132(交換2與3所得)——确定最右邊的位置，就剩下一位了，肯定确定了。

|——213(交換1與2所得)——231———————— 同上

|——321(交換1與3所得)——312———————— 同上

去除重複的全排列也很簡單，例如 ：

數字序列1232，交換1與第一個2，得(2)132，括号裡的2固定了，遞歸處理後面132序列的全排

數字序列還是1232，交換1與最後一個2，得(2)231，括号裡的2固定了，遞歸處理後面的231序列的全排

子序列132與231的全排肯定有重複的，這就是造成重複的原因

實作代碼：