leetcode里面应该有很多个与permutation相关的问题，那么首先就先写出一个全排列把。
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
道理其实很简单，就是简单的backtracking。其实用什么树去解释会让人越来越糊涂，我建议就是自己跟着迭代跑一遍，然后就会非常地清晰了。
但是在这个的基础上，leetcode又衍生出来许多其他的题型，下面就列举几个。
- 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"
这道题的意思就是求在全排列当中第k个排列，其实使用我们上面的代码就可以直接求出来:
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) {
// 先生成数组
vector<int> nums;
for(int i=0;i<n;i++) nums.push_back(i+1);
// 生成记录是否访问过的数组
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++类型当中，char和int类型是可以相互转换的：
内容为数字的char，包含
0,1,2,3,4,5,6,7,8,9
共计10个字符。
这十个字符在存为字符型时，其存储值为对应的ascii码，而这些ascii码是连续的，且按照其本身数字的大小来排列。
这样就可以将字符值，减去起始ascii码值实现转为对应值的效果。
设
int a; //转换的目标变量。
char c = '7'; //要转换的字符。
c = a - '0';
这样得到的就是对应的值了，即c = 7。
如果在文件中需要多次该操作，则可以定义一个带参宏，如下：
#define chartonumber(x) (x-'0')
这样只需要调用
c = chartonumber(a);
即可实现效果。
这样的答案显然是没有错误的，但是在这个题目当中，我们使用这个方法不幸就超时了，因为全排列呈爆炸性增长，对于我们的回溯法，需要的时间则是其平方次倍的，所以肯定会超时。
在这里就需要使用一些简单的数学技巧对我们的代码进行改动。
eg: array = {1,2, 3, 4} target: 寻找第九个排列组合.
观察我们的代码的迭代可以发现，在迭代过程当中，都是固定前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个
于是我们可以反推出来，当前循环到的前几位应该是什么。
例如让我们超时的输入为
n = 9, k = 331987
8! = 40320 k/8 = 8 k%8 = 9427
因此我们可以知道这个答案是以9开头的
然后接着计算下一位
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;
}
};
