Recursive solution


  • 0
    H

    Given k, we can compute the first digit x of a n-length string by dividing k by (n-1)!. Then we compute the permutation given n-1 and k-(x-1)*(n-1)! recursively. After getting the returned string S from this subproblem, we need to modify the string so that each digit in S that is greater than x will be increased by 1.

    string recursive(int n, int k, const vector<int>& nums) {
        if (n == 1)
            return "1";
        int first = (k-1) / nums[n-1] + 1;
        string rest_perm = recursive(n-1, k-(first-1)*nums[n-1], nums);
        for (int i = 0; i < rest_perm.length(); i ++)
            if (rest_perm[i] >= char(first+'0'))
                rest_perm[i] = char(rest_perm[i]+1);
        return char(first+'0') + rest_perm;
    }
    
    class Solution {
    public:
        string getPermutation(int n, int k) {
            vector<int> nums(n+1);
            nums[1] = 1;
            for (int i = 2; i <= n; i ++)
                nums[i] = i * nums[i-1];
            return recursive(n, k, nums);    
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.