Leetcode 60. Permutation Sequence

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 (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k , return the k ^th permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

思路： 看一个例子 n=4： k=15。每一个色块的大小都是(n-1)! = 6。k在第三个色块里，所以第1个数字是3。然后在紫色块中调用递归函数，这是我们剩余的数字是[124]，等价的 k = 15-6*2 = 3。边界条件是 len(nums) == 1。注意这个求在第几个色块里的操作是 (k-1)//factorial(n-1)，和求矩阵里的第k个元素是在哪一行哪一列类似。

 class Solution(object):

     def getPermutation(self, n, k):

         """

         :type n: int

         :type k: int

         :rtype: str

         """

         nums = list(range(1, n+1))

         res = []

         self.helper(nums, res, k)

         a = map(str, res)

         return ''.join(a)      

     def helper(self, nums, res, k):

         n = len(nums)

         if n == 1:

             res += nums

             return 

         i = (k-1)/math.factorial(n-1)

         res += [nums[i]]

         nums = nums[:i]+nums[i+1:]

         k = k - i*math.factorial(n-1)

         self.helper(nums, res, k)
         

另外一个算法就是用DFS一个一个的找，每次找到一个对于counter += 1。