Backtracking #2: kth Permutation

Cho một tập hơn gồm n số tự nhiên từ 1 tới n (n>1). Mỗi cách sắp xếp n phần tử này theo một thứ tự nào đó được gọi là một hoán vị của n phần tử.
Như vậy sẽ có n! hoán vị các bộ số mà mỗi bộ số chứa n số từ 1 tới n

Ví dụ với n=2, sẽ có 2 hoán vị là {1,2} và {2, 1}

Ví dụ với n=3, sẽ có 6 hoán vị là {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2} và {3,2,1}

Nhiệm vụ của bạn là tìm hoán vị thứ k của n phần tử (các hoán vị có thứ tự từ điển tăng dần)

Ví dụ:

• Với n=2 và k=1 thì kết quả kthPermutation(n,k)=[1,2]
• Với n=3 và k=5 thì kết quả kthPermutation(n,k)=[3,1,2]

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5 giây
• [Đầu vào] integer n, k
  Hai số tự nhiên n và k
1 <= n <= 6
1 <= k <= n!
• [Đầu ra] array.integer 
  Mảng chứa n phần tử thể hiện hoán vị thứ k (đếm từ 1)

Gợi ý:

• Bạn có thể làm bài tập bằng nhiều cách, nhưng ở đây muốn các bạn làm bằng backtracking (quay lui)
• Thuật toán này có thể tham khảo tại đây hoặc tại đây
• Cách làm đệ quy như sau:
  • Tư tưởng là sinh ra lần lượt tất cả các hoán vị từ 1 tới n. Tới khi đủ k hoán vị thì dừng lại
  • Xuất phát từ tập hợp rỗng. Dừng lại khi đủ n phần tử
  • Tại mỗi bước mà tập hợp chưa đủ n phần tử, hãy chọn thêm 1 phần tử mà chưa nằm trong tập hợp đó (ví dụ đang có 1 2 3 thì lần lượt chọn thêm 4 hoặc 5 hoặc 6)