# 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)     
        
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/math/pai-lie-zu-he/1643.-kth-smallest-instructions.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.