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 (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

方案一采用原始的递归回溯方法，发现TLE，方案二参考http://www.cnblogs.com/grandyang/p/4358678.html

class Solution {
private:
    void helper(int n, int& k, int cur, vector<bool>& visited, int& res) {
        if (k == 0) return;

        if (n == 0) {
            k--;
            if (k == 0)  res = cur;
            return;
        }

        for (int i = 1; i < int(visited.size()); i++) {
            if (visited[i])
                continue;
            visited[i] = true;
            helper(n - 1, k, cur * 10 + i, visited, res);
            visited[i] = false;
        }
    }
public:
    string getPermutation(int n, int k) {
        vector<bool> visited(n + 1, false);
        int res = 0;
        helper(n, k, 0, visited, res);
        return to_string(res);
    }
};

class Solution2{
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;
    }

};