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