Permutation Sequence

This approach involves generating all possible permutations of the numbers from 1 to n. We can use a recursive backtracking algorithm to find every permutation. As we generate them, we store them in a list. Since the standard backtracking approach of picking the smallest available number first generates permutations in lexicographical order, the k-th permutation will be the element at index k-1 in our list.

• Create a list to store the resulting permutations.
• Implement a recursive helper function, say backtrack(current_permutation, remaining_numbers).
• The base case for the recursion is when remaining_numbers is empty. At this point, a full permutation has been formed, so we add it to our list of permutations.
• In the recursive step, iterate through the remaining_numbers. For each number, add it to the current_permutation, remove it from remaining_numbers, and make a recursive call.
• After the recursive call returns, backtrack by removing the number from current_permutation and adding it back to remaining_numbers to explore other possibilities.
• The initial call will be with an empty permutation and a list of numbers from 1 to n.
• After the recursion completes, the list will contain all n! permutations in order. Return the string at index k-1.

class Solution {
    public String getPermutation(int n, int k) {
        List<String> permutations = new ArrayList<>();
        boolean[] used = new boolean[n + 1];
        generatePermutations(new StringBuilder(), n, permutations, used);
        return permutations.get(k - 1);
    }

    private void generatePermutations(StringBuilder current, int n, List<String> result, boolean[] used) {
        if (current.length() == n) {
            result.add(current.toString());
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!used[i]) {
                used[i] = true;
                current.append(i);
                generatePermutations(current, n, result, used);
                // Backtrack
                current.deleteCharAt(current.length() - 1);
                used[i] = false;
            }
        }
    }
}