Template Metaprogramming
Approach\n Describe your approach to solving the problem. \nUse template metaprogramming to precompute all relevant choose function values at compile time. For 
# Approach\n<!-- Describe your approach to solving the problem. -->\nUse template metaprogramming to precompute all relevant choose function values at compile time. For the actual algorithm during runtime, at every step, check if the number of instructions starting with `\'H\'` is at most `k`. If so, then the next instruction is `\'H\'`, otherwise it\'s `\'V\'` and the number of instructions starting with `\'H\'` should be subtracted from `k`.\n\nFor the template metaprogramming computation, `choose<N, M>::value` gives the value $$\\binom{N}{M}$$ and this is computed recursively with base cases defined for $$\\binom{N}{N}$$ and $$\\binom{N}{0}$$. A special case is added to set $$\\binom{0}{0}$$ to $$0$$ for the purpose of being a filler value for when the choose function recursion isn\'t applicable ($$M > N$$).\n\n`arr<N, ARGS...>::value` gives the array with values $$\\binom{N}{0},\\binom{N}{1},\\binom{N}{2},...$$. `arr2<ARGS...>::value` gives the 2d array where each row is generated from `arr<N, ARGS...>::value`. `arrGen<5, 0>` is used to recursively create a template list of consecutive integers from $$0$$ to $$2^5-1$$ which gets passed to the `arr2` struct, so this creates the 2d array of all choose function $$\\binom{N}{M}$$ where $$0\\leq N,M < 2^5$$.\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$ auxiliary space excluding template metaprogramming\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\ntemplate <int N, int M>\nstruct choose {\n    static constexpr int value = conditional<(M > N), choose<0, 0>, choose<N - 1, M>>::type::value + conditional<(M > N), choose<0, 0>, choose<N - 1, M - 1>>::type::value;\n};\n\ntemplate <int N>\nstruct choose<N, 0> {\n    static constexpr int value = 1;\n};\n\ntemplate <int N>\nstruct choose<N, N> {\n    static constexpr int value = 1;\n};\n\ntemplate <>\nstruct choose<0, 0> {\n    static constexpr int value = 0;\n};\n\ntemplate <int N, int... ARGS>\nstruct arr {\n    static constexpr array<int, sizeof...(ARGS)> value = {choose<N, ARGS>::value...};\n};\n\ntemplate <int... ARGS>\nstruct arr2 {\n    static constexpr array<array<int, sizeof...(ARGS)>, sizeof...(ARGS)> value = {arr<ARGS, ARGS...>::value...};\n};\n\ntemplate <int DEPTH, int... ARGS>\nstruct arrGen {\n    using type = arrGen<DEPTH - 1, ARGS..., (ARGS + sizeof...(ARGS))...>::type;\n};\n\ntemplate <int... ARGS>\nstruct arrGen<0, ARGS...> {\n    using type = arr2<ARGS...>;\n};\n\nstruct chooseArray {\n    static constexpr auto arr = arrGen<5, 0>::type::value;\n};\n\nclass Solution {\npublic:\n    string kthSmallestPath(vector<int>& destination, int k) {\n        int v = destination[0], h = destination[1];\n        string ans(h + v, \' \');\n        for (int i = 0; i < ans.size(); i++) {\n            if (v > 0 && k > chooseArray::arr[h + v - 1][v]) {\n                k -= chooseArray::arr[h + v - 1][v];\n                ans[i] = \'V\', v--;\n            } else {\n                ans[i] = \'H\', h--;\n            }\n        }\n        return ans;\n    }\n};\n```
['C++']