C++ Pascal Triangle
OK, I am not good at this - but I wanted to solve it on intuition (without looking into textbooks). Took me a while. This may not be the best solution - there a
OK, I am not good at this - but I wanted to solve it on intuition (without looking into textbooks). Took me a while. This may not be the best solution - there are several great math solutions with explanations in the discussion thread - check them out!\n\nInitially, I used "next_permutation" `k` times. That was too slow, obviously, but gave insight on how the string changes.\n\nLet\'s think about it - imagine you have "HHHHVVVV". How many steps do we need to get to these states:\n- "HHHVVVV**H**"?\n- "HHVVVV**HH**"?\n- "HVVVV**HHH**"?\n- "VVVV**HHHH**"?\n\nThese are the largest combinations with 4 "V" and `i` "H". We get to these states after we exhausted all combinations with:\n- 4 "V" and 1 "H" = nCr(4, 1) = 5 steps\n- 4 "V" and 2 "H" = nCr(4, 2) = 15 steps\n- 4 "V" and 3 "H" = nCr(4, 3) = 35 steps\n- 4 "V" and 4 "H" = nCr(4, 4) = 70 steps\n\n`nCr(a, b)` is the number of combinations to choose `b` elements out of `a`. I am using the Pascal Triangle with memoisation to compute this. You get `Comb` for free if you use Python, and you better know this method if you want to stick with C++.\n\nSo the idea is to find out how many "H" we can move all the way to the right within `k`. Now, if \'k\' is zero - we construct and return the string - easy. \n\nOtherwise, we need to do one more step. What is the next permutation for "HHHVVVV**H**" (`i == 1`) ? It\'s "HH**V**HHVVV". The first "V" is in its final position, and the rest of the string - the smallest combination of remaining Hs and Vs. So, we keep `i + 1` "H", add 1 "V", and call `kthSmallestPath` for remaining "H", "V" and `k`.\n\nExample: [4, 4], k == \'9\'.\n1. 5 steps to get from "HHHHVVVV" to "HHHVVVV**H**", `i == 1`. \n2. Keep "HHV", and call our function for [2, 3], `k == 4`.\n3. 4 steps to get from "HHVVV" to "HVVV**H**", `i == 1`.\n4. `k == 0`, return "HVVVH".\n5. Combine strings, the final result is "HHV" + "HVVVH".\n\n**C++**\n```cpp\nint dp[17][17] = {};\nclass Solution {\n    int nCr(int i, int j) {\n        if (i == 1 || j == 1)\n            return 1;\n        return dp[i][j] ? dp[i][j] : dp[i][j] = nCr(i - 1, j) + nCr(i, j - 1);\n    }\npublic:\n    string kthSmallestPath(vector<int>& d, int k) {\n        int h = d[1], v = d[0], cur = 1, i = 1;\n        for (; i <= h; ++i) {\n            if (nCr(v + 1, i + 1) > k)\n                break;                \n            cur = nCr(v + 1, i + 1);\n        }\n        if (k - cur == 0)\n            return string(h - i + 1, \'H\') + string(v, \'V\') + string(i - 1, \'H\');\n        return string(h - i, \'H\')  + "V" + kthSmallestPath(vector<int>() = {v - 1 , i}, k - cur);\n    }\n};\n```
[]