60. Permutation Sequence

Backtracking

class Solution {
    int count = 0;
    String result = "";

    public String getPermutation(int n, int k) {
        boolean[] used = new boolean[n + 1]; // mark if each number cound be used
        backtracking(n, k, "", used);
        return result;
    }


    private void backtracking(int n, int k, String s, boolean[] used) {
        if (s.length() == n) {
            count++;
            if (count == k) {
                result = s;
            }
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (used[i]) continue;
            used[i] = true;
            backtracking(n, k, s + i, used);
            if (!result.isEmpty()) return; // exit after find the kth result
            used[i] = false;
        }
    }
}

Remarks:

1. TC: $O(n!)$, SC: $O(n)$.
2. Java string: "124" + 1 = "1241"
3. State to be saved as parameters: (a) current string, (b) used nums

Math

class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            nums.add(i);
        }

        // creacte factorial array
        int[] factorial = new int[n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }

        k--; // set k index from 0
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= n; i++) {
            // find the index of the number
            int idx = k / factorial[n - i];
            // get the number(1-n) from the array and remove it  
            sb.append(nums.get(idx));
            nums.remove(idx);
            // update k to process the next digit
            k %= factorial[n - i];
        }

        return sb.toString();
    }
}

Remarks:

1. TC: $O(n^2)$ (everytime we remove a number idx from the array, it takes $O(n)$), SC: $O(n)$.
2. Idea:
   Assume all permutations is $n!$, then the permutation of each numbers being placed at the first position is $(n-1)!$. So we can detemine the numbers digit by digit, from left to right.