1643. Kth Smallest Instructions Hard

1/**
2 * [1643] Kth Smallest Instructions
3 *
4 * 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.
5 * The instructions are represented as a string, where each character is either:
6 * 
7 * 	'H', meaning move horizontally (go right), or
8 * 	'V', meaning move vertically (go down).
9 * 
10 * Multiple instructions will lead Bob to destination. For example, if destination is (2, 3), both "HHHVV" and "HVHVH" are valid instructions.
11 * However, Bob is very picky. Bob has a lucky number k, and he wants the k^th lexicographically smallest instructions that will lead him to destination. k is 1-indexed.
12 * Given an integer array destination and an integer k, return the k^th lexicographically smallest instructions that will take Bob to destination.
13 *  
14 * Example 1:
15 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/12/ex1.png" style="width: 300px; height: 229px;" />
16 * 
17 * Input: destination = [2,3], k = 1
18 * Output: "HHHVV"
19 * Explanation: All the instructions that reach (2, 3) in lexicographic order are as follows:
20 * ["HHHVV", "HHVHV", "HHVVH", "HVHHV", "HVHVH", "HVVHH", "VHHHV", "VHHVH", "VHVHH", "VVHHH"].
21 * 
22 * Example 2:
23 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/12/ex2.png" style="width: 300px; height: 229px;" />
24 * 
25 * Input: destination = [2,3], k = 2
26 * Output: "HHVHV"
27 * 
28 * Example 3:
29 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/12/ex3.png" style="width: 300px; height: 229px;" />
30 * 
31 * Input: destination = [2,3], k = 3
32 * Output: "HHVVH"
33 * 
34 *  
35 * Constraints:
36 * 
37 * 	destination.length == 2
38 * 	1 <= row, column <= 15
39 * 	1 <= k <= nCr(row + column, row), where nCr(a, b) denotes a choose b​​​​​.
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/kth-smallest-instructions/
45// discuss: https://leetcode.com/problems/kth-smallest-instructions/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn kth_smallest_path(destination: Vec<i32>, k: i32) -> String {
51        String::new()
52    }
53}
54
55// submission codes end
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_1643() {
63    }
64}
65