# 1643. Kth Smallest Instructions

Bob is standing at cell `(0, 0)`, and he wants to reach `destination`: `(row, column)`. He can only travel **right** and **down**. You are going to help Bob by providing **instructions** for him to reach `destination`.

The **instructions** are represented as a string, where each character is either:

* `'H'`, meaning move horizontally (go **right**), or
* `'V'`, meaning move vertically (go **down**).

Multiple **instructions** will lead Bob to `destination`. For example, if `destination` is `(2, 3)`, both `"HHHVV"` and `"HVHVH"` are valid **instructions**.

*

However, Bob is very picky. Bob has a lucky number `k`, and he wants the `kth` **lexicographically smallest instructions** that will lead him to `destination`. `k` is **1-indexed**.

Given an integer array `destination` and an integer `k`, return *the* `kth` ***lexicographically smallest instructions** that will take Bob to* `destination`.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/10/12/ex1.png)

```
Input: destination = [2,3], k = 1
Output: "HHHVV"
Explanation: All the instructions that reach (2, 3) in lexicographic order are as follows:
["HHHVV", "HHVHV", "HHVVH", "HVHHV", "HVHVH", "HVVHH", "VHHHV", "VHHVH", "VHVHH", "VVHHH"].
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/10/12/ex2.png)

```
Input: destination = [2,3], k = 2
Output: "HHVHV"
```

**Example 3:**

![](https://assets.leetcode.com/uploads/2020/10/12/ex3.png)

```
Input: destination = [2,3], k = 3
Output: "HHVVH"
```

**Constraints:**

* `destination.length == 2`
* `1 <= row, column <= 15`
* `1 <= k <= nCr(row + column, row)`, where `nCr(a, b)` denotes `a` choose `b`​​​​​.

从格子(0,0)可向下或向右走到(v,h)处，向下的指令V，向右指令为H，问所有指令序列中字典序排第K小的。无论怎么走最后都需要v个V和h个H，而当字符串中每一种字符的数量固定时，求字典序第 k 小的字符串，可以从高位向低位依次确定每一个位置的字符。当在最高位放置V，那所有最高位为 H 的字符串的字典序都比它小，这样的字符串共有comb(h + v - 1, h - 1)个，即剩余 h+v-1个位置中选择 h-1个放入 H，其余位置自动放入 V方案数。因此如果 k大于这个组合数，那么最高位一定是V，v--，k -= comb；如果 k小，最高位是H, h-=1，但不需要改变 k 的值，因为剩余部分就是包含 (h-1,v)的字典序第 k 小的字符串。

参考自[zerotrac2](https://link.zhihu.com/?target=https%3A//leetcode-cn.com/problems/kth-smallest-instructions/solution/di-k-tiao-zui-xiao-zhi-ling-by-zerotrac2/)。

```python
from math import comb

class Solution:
    def kthSmallestPath(self, destination: List[int], k: int) -> str:
        v, h = destination
        res = []
        for _ in range(h + v):
            if h == 0:
                res.append('V')
                v -= 1
                continue
            elif v == 0:
                res.append('H')
                h -= 1
                continue
            c = comb(h + v - 1, h - 1)
            if k > c:
                res.append('V')
                v -= 1
                k -= c
            else:
                res.append('H')
                h -= 1
        return ''.join(res)     
        
```
