60. Permutation Sequence

关联问题：排列1：46. Permutations， 排列2：47. Permutations II，组合：77. Combinations 

问题：

给定数字1～n，求他们组成的第k个排列。

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.

 

Example 1:
Input: n = 3, k = 3
Output: "213"

Example 2:
Input: n = 4, k = 9
Output: "2314"

Example 3:
Input: n = 3, k = 1
Output: "123"
 

Constraints:
1 <= n <= 9
1 <= k <= n!

　　

解法：Backtracking（回溯算法）

对于本问题，两个变量：

• 路径：已经选择好的前几位结果
• 选择列表：对每个位置上元素的选择可能性0～n，排除已经visited过的元素

处理过程：

• base：递归退出条件：选择到最后一位结束，这里为已经选择好路径长度==给出的数组长度。
  • 这里计数得到满足条件的排序，=k时，返回。
• 做选择：对于当前位置，选择其中一个可用数字a。
  • 路径.add(a)
  • 选择列表.delete(a)
• 撤销选择：回退到选择数字a之前的状况。
  • 路径.delete(a)
  • 选择列表.add(a)

代码参考：

class Solution {
public:
    void backtrack(string& res, int& count, int n, int k, string& path, vector<int>& visited) {
        if(path.size() == n) {
            count++;
            if(count==k) {
                res = path;
            }
            return;
        }
        for(int i=0; i<n; i++) {
            if(!visited[i]) {
                char opt = '1'+i;
                visited[i] = 1;
                path+=opt;
                backtrack(res, count, n, k, path, visited);
                if(res.size()>0) return;
                path.pop_back();
                visited[i] = 0;
            }
        }
        return;
    }
    string getPermutation(int n, int k) {
        string res;
        string path("");
        int count = 0;
        vector<int> visited(n, 0);
        backtrack(res, count, n, k, path, visited);
        return res;
    }
};