# leetcode\_60

## 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:

```
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth 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

1. **dfs with pruning**
2. Note: we cannot use `swap` as we did in `problem 46` where the ordering of permutations is not required. for example:
   * `1 2 3` swapped `1` with `3` will be `3 2 1`, the ordering of `1` and `2` is changed due to the swap, the permutaion order will not be guaranteed when we choose the next number. ie. 2 will be choosed before 1.
   * Thus we use a `seen` hashset to record which number has been used in the current permutation.
3. Inorder to speed up the backtracking process or eliminate unnecessary backtrackings, we can pre-calculate the number of permutations will be generated in each recursive call and skip to the right recursive call where the target permutations will be created.

```cpp
class Solution {
public:
    vector<bool> seen;
    vector<int> factoral;
    int cur = 0;

    void dfs(int n, int k, string & permute) {
        for (int i = 0; i < n; i++) {
            if (seen[i]) continue;
            int num = factoral[n - permute.size() - 1];
            // reaches the answer when cur + num == k
            if (cur + num < k) {
                cur += num;
                continue;
            }
            seen[i] = true;
            permute.push_back('1' + i);
            dfs(n, k, permute);
            // no need to pop_back() or seen, their is no tackback process
        }
    }
    string getPermutation(int n, int k) {
        seen = vector<bool>(n);
        factoral = vector<int>(n + 1, 1);
        for (int i = 1; i <= n; i++)
            factoral[i] = factoral[i - 1] * i;

        string permute;
        dfs(n, k, permute);
        return permute;
    }
};
```

1. **finding every digit**
2. Though the intrinsic idea are the same as the first solution, the first solution follows a backtracking strategy but with efficient pruning, while this solution trys to find every digit in the final permutation in a iterative way.
3. use 0-based indexing to faciliate the calculation.
   * for example, when the group size is `2`.
   * 1-based. `5 / 2  == 4 / 2`. 5 and 4 are within the same group which is incorrect.
   * 0-based. `(5 - 1) / 2 != (4 - 1) / 2`.

```cpp
class Solution {
public:
    string getPermutation(int n, int k) {
        int factoral[n + 1] = {1};
        for (int i = 1; i <= n; i++)
            factoral[i] = factoral[i - 1] * i;

        vector<int> nums{'1', '2', '3', '4', '5', '6', '7', '8', '9'};
        string res;

        k = k - 1;
        for (int i = 0; i < n; i++) {
            int index = (k / factoral[n - i - 1]);
            res += nums[index];
            k = k - index * factoral[n - i - 1];
            // to ensure each number is used only once
            nums.erase(nums.begin() + index);
        }

        return res;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhongquan789.gitbook.io/leetcode/leetcode/leetcode_60.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.