第K个n的排列

package main
//import "fmt"
import "strconv"
// import "sort"
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param k int整型 
 * @return string字符串
*/
func KthPermutation( n int ,  k int ) string {
    ans:=""
    vis:=map[int]bool{}
    var dfs func(string)
    dfs=func(s string){
        if ans!=""{
            return
        }
        if len(s)==n{
            k--
            if k==0{
                ans=s
            }
            return
        }
        for i:=1;i<=n;i++{
            if vis[i]{
                continue
            }
            s+=strconv.Itoa(i)
            vis[i]=true
            dfs(s)
            s=s[:len(s)-1]
            vis[i]=false
        }
    }
    dfs("")
    return ans
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @return string字符串
     */
    int num = 0;
    void recursion(vector<string>& S, const string& s, string& str, vector<int>& v){
        if(str.length() == s.length()){
            S.push_back(str);
            return;
        }
        for(int i=0; i<s.length(); i++){
            if(v[i]){
                continue;
            }
            str.push_back(s[i]);
            v[i] = 1;
            recursion(S, s, str, v);
            str.pop_back();
            v[i] = 0;
        }
    }
    string KthPermutation(int n, int k) {
        // write code here
        string s = "";
        for(int i=1; i<=n; i++){
            s += i + '0';
        }
        string str = "";
        vector<string> S;
        vector<int> v(s.length(), 0);
        recursion(S, s, str, v);
        //sort(S.begin(), S.end());
        return S[k-1];
    }
};

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @param k int整型
# @return string字符串
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/1595969179464e4c940a90b36abb3c54?tpId=196&tqId=40457&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        定义dfs[pos]表示当前将要在位置pos放置字符，定义visited[i]表示位置i的字符是否访问过。
        初始时刻，pos = 0
        边界条件：
            如果当前放置位置为n，说明字符串s的所有字符已经放置完毕，即找到1组解，加入结果集res
        剪枝：
            当res的长度为k时，说明已经找到答案，直接返回
    复杂度：
        时间复杂度：O(n * k)
        空间复杂度：O(n)
    """

    def KthPermutation(self, n, k):
        # write code here
        def dfs(idx):
            if idx == n:
                res.append("".join(combine[:]))
                return
            if len(res) == k: # 剪枝，我们只需要找到第k组排列就可以了
                return
            for i in range(1, n + 1):
                if i not in visited:
                    combine.append(str(i))
                    visited.add(i)
                    dfs(idx + 1)
                    combine.pop()
                    visited.remove(i)

        visited, combine, res = set(), [], []
        dfs(0)

        n = len(res)
        return res[k % n - 1]


if __name__ == "__main__":
    sol = Solution()

    # n, k = 5, 3

    n, k = 5, 25

    res = sol.KthPermutation(n, k)

    print res