060 - Permutation Sequence

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 k^th permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
Hide Tags
Backtracking Math
Hide Similar Problems
(M) Next Permutation (M) Permutations

第一反应当然是回溯，当然也毫无悬念地超时了。
那就琢磨一下更简洁的规律吧：
从回溯里打印出所有的组合，发现从最高位依次向下看 k，每个位置的可能性都是（当前位 – 1）的阶乘。
     例如第三位选定了某个数字，剩下的两位就只有两种可能的组合；第四位选定了，剩下的三位就有 6 种组合。
这就是说，最高位的值，应该是当前的 k 除以次高位位数的阶乘。
    例如 n=9, k=278082，278082/(8!) = 6，最高位就是第 [6] 个数字，也就是 7。（当然，应该先把 278082 减去 1， 因为所有结果排列也是从第 0 种开始的）
    然后，对于下一位，就可以用 k 对于 (8!) 的余数，来作为新的 k 值，代入同样的计算就可以了。
    算出商之后，去取出对应的数字的时候，需要跳过已经选择的数字，因此下标不能直接用商，需要计算一下。
算到全部数字用完，结果就出来啦！

class Solution {
public:
    string getPermutation(int n, int k) {
        string rst="";
        bool used[9]={false};
        int fact[10]={1, 1, 1, 2, 6, 24, 120, 720, 5040, 40320};        k--;
        for(int ii=n; ii>0; ii--)
        {
            int idx = k/fact[ii];
           
            for(int uu=0; uu<n; ++uu)
                if(false==used[uu])
                {
                    if(!idx)
                        rst += to_string(uu+1), used[uu]=true;
                    idx--;
                }
           
            k=k%fact[ii];
        }
        return rst;
    }
    //-------------------------------------- backtracing TLE --------------------------------------
    string getPermutation_timeout(int n, int k) {
        string rst;
        vector<int> buf;
        vector<bool> used(n, 0);
        build(n, used, 0, k, buf, rst);
        return rst;
    }
   
    bool build(int sz, vector<bool>& used, int count, int& k, vector<int>& buf, string& rst)
    {
        if(count==sz)
            return (0==(--k));
        else
        {
            for(int ii=0; ii<sz; ++ii)
            {
                if(false==used[ii])
                {
                    used[ii]=true;
                    rst.push_back((char)(ii+'1'));
                    if(true == build(sz, used, count+1, k, buf, rst))
                        return true;
                    rst.pop_back();
                    used[ii]=false;
                }
            }
        }
        return false;
    }
};
0 ms.