60. Permutation Sequence #

Problem #

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.

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"

Problem Summary #

Given the set [1,2,3,…,n], all its elements have a total of n! permutations.

List all permutations in order and label them one by one. When n = 3, all permutations are as follows: “123”, “132”, “213”, “231”, “312”, “321”. Given n and k, return the kth permutation.

Solution Approach #

Use DFS to brute-force enumerate. This approach has a particularly high time complexity; consider a better solution.

Code #


package leetcode

import (
	"fmt"
	"strconv"
)

func getPermutation(n int, k int) string {
	if k == 0 {
		return ""
	}
	used, p, res := make([]bool, n), []int{}, ""
	findPermutation(n, 0, &k, p, &res, &used)
	return res
}

func findPermutation(n, index int, k *int, p []int, res *string, used *[]bool) {
	fmt.Printf("n = %v index = %v k = %v p = %v res = %v user = %v\n", n, index, *k, p, *res, *used)
	if index == n {
		*k--
		if *k == 0 {
			for _, v := range p {
				*res += strconv.Itoa(v + 1)
			}
		}
		return
	}
	for i := 0; i < n; i++ {
		if !(*used)[i] {
			(*used)[i] = true
			p = append(p, i)
			findPermutation(n, index+1, k, p, res, used)
			p = p[:len(p)-1]
			(*used)[i] = false
		}
	}
	return
}