Backtracking - 60. Permutation Sequence

leetcode
72

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 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.
  • 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"

思路：

题目意思是给一个整数n，求出1-n内所有组合的第k大的组合，最直观的方法可以使用回溯，把所有的结果都求出来再去找第k大， 但是这一题可以用其他技巧解决，因为是由n的阶乘，所以很容易得出：f[i] = f[i-1]*i，只要通过阶乘来判断要找到的数在最高位之外的数的所有组合中的位置，就能得到结果。

代码：

go：

func getPermutation(n int, k int) string {

    var res int 
    var nums []int
    var fact = 1
    for i := 1; i <= n; i++ {
        fact *= i
        nums = append(nums, i)
    }
    
    l := k - 1
    for i := 0; i < n; i++ {
        fact /= (n - i)
        idx := (l / fact)
        res = res * 10 + nums[idx]
        nums = append(nums[0:idx], nums[idx+1:]...)
        l -= idx * fact
    }
    
    return strconv.Itoa(res)
}