[LeetCode]Permutation Sequence

[cpp]
class Solution {
//decompose the big problem into smaller problem
private:
vector numT;//keep record of number state, choosen or not
vector factT;//save factorial number
public:
string getPermutation(int n, int k) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
Init(n);
string ans;
getPermutation_Aux(n, k, 1, ans);
return ans;
}

void getPermutation_Aux( int n, int k, int selectNow, string& ans)
{
if(n == 0) return;
if (factT[n-1] >= k)//then the first digit should be pq.front()
{
int now = selectNow;
ans.append(1, now+'0');
numT[selectNow] = false;
selectNow = SelectMin();
getPermutation_Aux(n-1, k, selectNow, ans);
}
else
{
selectNow = MoveForward(selectNow);
getPermutation_Aux(n, k-factT[n-1], selectNow, ans);
}
}

int SelectMin( )
{
for(int i = 1; i < numT.size(); ++i)
if(numT[i]) return i;
return -1;
}

int MoveForward(int startIdx )
{
for (int i = startIdx+1; i < numT.size(); ++i)
if(numT[i]) return i;
return -1;
}

void Init( int n )
{
numT.clear();//very important, without this line, it will be Runtime Error
factT.clear();//very important, without this line, it will be Runtime Error
numT.resize(n+1, true);

int tmp = 1;
factT.resize(n+1);
factT[0] = 1;
for(int i = 1; i <= n; ++i)
{
tmp *= i;
factT[i] = tmp;
}
}
};

class Solution {
//decompose the big problem into smaller problem
private:
vector numT;//keep record of number state, choosen or not
vector factT;//save factorial number
public:
string getPermutation(int n, int k) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
Init(n);
string ans;
getPermutation_Aux(n, k, 1, ans);
return ans;
}

void getPermutation_Aux( int n, int k, int selectNow, string& ans)
{
if(n == 0) return;
if (factT[n-1] >= k)//then the first digit should be pq.front()
{
int now = selectNow;
ans.append(1, now+'0');
numT[selectNow] = false;
selectNow = SelectMin();
getPermutation_Aux(n-1, k, selectNow, ans);
}
else
{
selectNow = MoveForward(selectNow);
getPermutation_Aux(n, k-factT[n-1], selectNow, ans);
}
}

int SelectMin( )
{
for(int i = 1; i < numT.size(); ++i)
if(numT[i]) return i;
return -1;
}

int MoveForward(int startIdx )
{
for (int i = startIdx+1; i < numT.size(); ++i)
if(numT[i]) return i;
return -1;
}

void Init( int n )
{
numT.clear();//very important, without this line, it will be Runtime Error
factT.clear();//very important, without this line, it will be Runtime Error
numT.resize(n+1, true);

int tmp = 1;
factT.resize(n+1);
factT[0] = 1;
for(int i = 1; i <= n; ++i)
{
tmp *= i;
factT[i] = tmp;
}
}
};