60. Permutation Sequence

• Difficulty: Medium

• Topics: Math, Backtracking

• Similar Questions:

  • Next Permutation

  • Permutations

Problem:

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:

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.
• 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"

Solutions:

class Solution {
public:
    string getPermutation(int n, int k) {
        string digits = "123456789";
        digits = digits.substr(0, n);
        if (n == 1) return "1";
        int base = 1;
        for (int i = 1; i < n; ++i) {
            base *= i;
        }

       helper(digits, base, k - 1);
        return ret;
    }

    void helper(string& digits, int base, int k) {
        cout << base << endl;
       if (digits.length() == 0)    return; 
        int index = k/base;
        ret.push_back(digits[index]);
        digits.erase(index, 1);
        if (digits.length() == 1) {
            ret.push_back(digits[0]);
            return;
        }
        int newBase = base/(digits.length());
        helper(digits, newBase, k - index * base);
    }
private:
    string ret;

};