C++ O((r + c)^2) solution with explanation
We can restate this problem as finding the k th string in lexicographic order among strings consisting of c \u201CV\u201Ds and r \u201CH\u201Ds. Let s(r, c, k) 
We can restate this problem as finding the ```k``` th string in lexicographic order among strings consisting of ```c``` \u201CV\u201Ds and ```r``` \u201CH\u201Ds. Let ```s(r, c, k)``` denote the answer string for inputs ```r, c, k```. \n\nNote that if ```r == 0```, the only possible string is that having ```c``` \u201CH\u201Ds and if ```c == 0```, the only possible string is that having ```r``` \u201CV\u201Ds. So, these two cases can be handled easily. Now we come to the case where both ```r``` and ```c``` and non-zero. \nNote that all strings starting with \u201CH\u201D appear before those starting with \u201CV\u201D. To find the number of strings starting with \u201CH\u201D, we place \u201CH\u201D in the first position, and compute the number of strings of length ```r + c - 1``` which can be formed using ```c-1``` \u201CH\u201Ds and ```r``` \u201CV\u201Ds. This is given by ```nCr(r + c - 1, c-1)```. \n\nSo, if ```k <= nCr(r + c - 1, c-1)```, we know that the answer starts with an \u201CH\u201D. Having placed \u201CH\u201D in the first position, we can forget about it, and solve the problem of constructing the string having ```r``` \u201CV\u201Ds and ```c-1``` \u201CH\u201Ds (because we used one up). Because all strings starting with \u201CH\u201D appear at the top of the list, and we know that the answer starts with an \u201CH\u201D, the ```k``` th string in the list of strings of size ```r + c``` will be the ```k``` th string in the list of strings of size ```r + c - 1```. So, the answer is ``` \u201CH\u201D + s(r, c-1, k)```. \n\nIf ```k > nCr(r + c - 1, c-1)```, then we know that it starts with a \u201CV\u201D. Having placed one \u201CV\u201D, we consider the problem of creating strings of size ```r + c - 1```, using ```r - 1``` \u201CV\u201Ds and ```c``` \u201CH\u201Ds. Now, because we have removed the ```nCr(r + c - 1, c-1)``` strings starting with \u201CH\u201D, the ```k``` th string in the list of strings of size ```r + c``` will be the ```k - nCr(r + c - 1, c-1)``` th string in the list of strings of size ```r + c - 1```. So, the answer in this case is ``` \u201CV\u201D + s(r-1, c-1, k - nCr(r + c - 1, c-1))```.\n\nThe only \u201Ctrick\u201D here is to precompute values of ```nCr``` by using the relationship ```nCr(a, b) = nCr(a-1, b) + nCr(a-1, b-1)```. That way, when performing the recursion to construct the strings, we can just query these values instead of recomputing them.\n\nThe time complexity of constructing strings is ```O(r+c)```, because at each step, either ```r``` or ```c``` decreases by 1. The time complexity of computing all relevant ```nCr``` values is ```O((r+c)^2)```, but in this case it is practically constant because we know ```0 <= r + c <= 15```.\n```\nclass Solution {\n    vector<vector<long long int>> chooses;\n    string help(int r, int c, int k){\n        if (c == 0)\n            return string(r, \'V\');\n\n        if (r == 0)\n            return string(c, \'H\');\n\n        if (k <= chooses[r+c-1][c-1])\n            return "H" + help(r, c-1, k);\n        \n        return "V" + help(r-1, c, k - chooses[r+c-1][c-1]);\n    }\npublic:\n    string kthSmallestPath(vector<int>& destination, int k) {\n        chooses = vector<vector<long long int>>(40, vector<long long int>(40));\n        for (int i = 0; i <= 35; ++i){\n            chooses[i][0] = chooses[i][i] = 1;\n        }\n        for (int i = 2; i <= 35; ++i){\n            for (int j = 1; j <= i/2; ++j){\n                chooses[i][j] = chooses[i-1][j] + chooses[i-1][j-1];\n                chooses[i][i-j] = chooses[i][j];\n            }\n        }\n        return help(destination[0], destination[1], k);\n    }\n};\n\n```\n
[]