60. Permutation Sequence - cocoder39/coco39_LC GitHub Wiki

123
132
213
231
312
321

there are 3! = 6 sequences, there are 2! = 2 sequences that starts with 1...

string getPermutation(int n, int k) {
        vector<int> arr(n + 1); //arr[i] = i!
        arr[0] = 1;
        for (int i = 1; i <= n; i++) {
            arr[i] = i * arr[i - 1];
        }
        
        string nums(n, '0');
        for (int i = 0; i < n; i++) {
            nums[i] += i + 1;
        }
        
        string res;
        k--;
        k %= arr[n];
        for (int i = n - 1; i >= 0; i--) {
            int idx = k / arr[i];
            res.push_back(nums[idx]);
            k %= arr[i];
            nums.erase(nums.begin() + idx);
        }
        return res;
    }