leetcode里面應(yīng)該有很多個與permutation相關(guān)的問題，那么首先就先寫出一個全排列把。

code:
#include <iostream>
#include <vector>
using namespace std;

void helper(vector<int>& nums, vector<int> rec, vector<vector<int>>& ans, vector<int> visited){
        if( rec.size() == nums.size() ){
                ans.push_back(rec);
        }
        else{
                for(int i=0; i<nums.size(); i++){
                        if( visited[i] == 1 ) continue;
                        else{
                                rec.push_back( nums[i] );
                                visited[i] = 1;
                                helper(nums, rec, ans, visited);
                                rec.pop_back();
                                visited[i] = 0;
                        }
                }
        }
}

int main(int argc, char const *argv[])
{
        /* code */
        // generate a permutation using backtracing
        vector<int> nums = {1, 2, 3, 4};
        vector<int> rec;
        vector<int> visited = {0, 0, 0, 0};
        vector< vector<int> > ans;
        helper( nums, rec, ans, visited);
        int counter = 0;
        for(auto a : ans){
                counter ++;
                for( auto i : a ){
                        cout << i << " ";
                }
                cout << endl;
        };
        cout<< "Total Num is: "<< counter << endl;
        return 0;
}

output:
1 2 3 4 
1 2 4 3 
1 3 2 4 
1 3 4 2 
1 4 2 3 
1 4 3 2 
2 1 3 4 
2 1 4 3 
2 3 1 4 
2 3 4 1 
2 4 1 3 
2 4 3 1 
3 1 2 4 
3 1 4 2 
3 2 1 4 
3 2 4 1 
3 4 1 2 
3 4 2 1 
4 1 2 3 
4 1 3 2 
4 2 1 3 
4 2 3 1 
4 3 1 2 
4 3 2 1 
Total Num is: 24

道理其實(shí)很簡單，就是簡單的backtracking。其實(shí)用什么樹去解釋會讓人越來越糊涂，我建議就是自己跟著迭代跑一遍，然后就會非常地清晰了。
但是在這個的基礎(chǔ)上，leetcode又衍生出來許多其他的題型，下面就列舉幾個。

60. Permutation Sequence

The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.
Example 1:

Input: n = 3, k = 3
Output: "213"
Example 2:

Input: n = 4, k = 9
Output: "2314"

這道題的意思就是求在全排列當(dāng)中第k個排列，其實(shí)使用我們上面的代碼就可以直接求出來:

class Solution {
    void helper(vector<int>& nums, vector<int> rec, vector<vector<int>>& ans, vector<int> visited){
        if( rec.size() == nums.size() ){
                ans.push_back(rec);
        }
        else{
                for(int i=0; i<nums.size(); i++){
                        if( visited[i] == 1 ) continue;
                        else{
                                rec.push_back( nums[i] );
                                visited[i] = 1;
                                helper(nums, rec, ans, visited);
                                rec.pop_back();
                                visited[i] = 0;
                        }
                }
        }
}
public:
    string getPermutation(int n, int k) {
        // 先生成數(shù)組
        vector<int> nums;
        for(int i=0;i<n;i++) nums.push_back(i+1);
        // 生成記錄是否訪問過的數(shù)組
        vector<int> visited(n);
        vector< vector<int>> ans;
        vector<int> rec;
        
        helper( nums, rec, ans, visited);
        string result;
        // 輸出答案
        for( auto a: ans[k-1] ){
            result.push_back((char)(a + '0'));
        }
        return result;
    }
};

這里有個需要注意的地方，在C++類型當(dāng)中，char和int類型是可以相互轉(zhuǎn)換的：

內(nèi)容為數(shù)字的char，包含
0,1,2,3,4,5,6,7,8,9
共計(jì)10個字符。
這十個字符在存為字符型時，其存儲值為對應(yīng)的ascii碼，而這些ascii碼是連續(xù)的，且按照其本身數(shù)字的大小來排列。
這樣就可以將字符值，減去起始ascii碼值實(shí)現(xiàn)轉(zhuǎn)為對應(yīng)值的效果。
設(shè)
int a; //轉(zhuǎn)換的目標(biāo)變量。
char c = '7'; //要轉(zhuǎn)換的字符。
c = a - '0';
這樣得到的就是對應(yīng)的值了，即c = 7。
如果在文件中需要多次該操作，則可以定義一個帶參宏，如下：
#define chartonumber(x) (x-'0')
這樣只需要調(diào)用
c = chartonumber(a);
即可實(shí)現(xiàn)效果。

這樣的答案顯然是沒有錯誤的，但是在這個題目當(dāng)中，我們使用這個方法不幸就超時了，因?yàn)槿帕谐时ㄐ栽鲩L，對于我們的回溯法，需要的時間則是其平方次倍的，所以肯定會超時。
在這里就需要使用一些簡單的數(shù)學(xué)技巧對我們的代碼進(jìn)行改動。

eg: array = {1,2, 3, 4} target: 尋找第九個排列組合.
觀察我們的代碼的迭代可以發(fā)現(xiàn)，在迭代過程當(dāng)中，都是固定前n位求解后面(array.length - n)位的排列，然后連接到前面形成答案。
eg:固定第一位為 1 排列有 
1 2 3 4 
1 2 4 3 
1 3 2 4 
1 3 4 2 
1 4 2 3 
1 4 3 2 
一共等于 3! = 6 個
固定前兩位為 1 2 排列有
1 2 3 4 
1 2 4 3 
2！= 2個
于是我們可以反推出來，當(dāng)前循環(huán)到的前幾位應(yīng)該是什么。
例如讓我們超時的輸入為 
n = 9, k = 331987
8! = 40320    k/8 = 8   k%8 = 9427
因此我們可以知道這個答案是以9開頭的
然后接著計(jì)算下一位
9427 7! = 5040   9427/7! = 1  9427%7! = 4387 
所有我們可以知道前兩位是92了
然后以此類推。。 
a1 = k / (n - 1)!
k1 = k

a2 = k1 / (n - 2)!
k2 = k1 % (n - 2)!
...

an-1 = kn-2 / 1!
kn-1 = kn-2 % 1!

an = kn-1 / 0!
kn = kn-1 % 0!

開始愉快地寫代碼

class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        string num = "123456789";
        vector<int> f(n, 1);
        for (int i = 1; i < n; ++i) f[i] = f[i - 1] * i;
        --k;
        for (int i = n; i >= 1; --i) {
            int j = k / f[i - 1];
            k %= f[i - 1];
            res.push_back(num[j]);
            num.erase(j, 1);
        }
        return res;
    }
};