[C++] Combinatorial Solution with explanation
A path that leads to the destination is a binary string (each position can contain one of only two chars H or V)\nDefine:\nV = destination[0] = number of vertic
A path that leads to the destination is a binary string (each position can contain one of only two chars H or V)\nDefine:\n`V = destination[0]` = number of vertical steps to be taken and, \n`H = destination[1]` = number of horizontal steps to be taken\n`N = H + V`              = total path length\n\nnumber of paths = `nCk(N,H) = N! / ((N-H)! * H!) = nCk(N,V) = N! / ((N-V)! * V!)`\n\n\nTake the example: `H=3, V=2, k=4`\n`path = _ _ _ _ _`\nWhere `path[i]` represents the `i-th` step\n\nInitial state: `H=3, V=2, k=4`\nStart completing the path from left to right. \nLet\'s try adding `H` as the first step, `path_tmp = H _ _ _ _`\nIf we fix this, number of valid paths that have `H` in the first location = `nCk(H+V-1, max(H-1,V))  = nCk(4, max(2,2)) = nCk(4,2) = 6`\nWhich means there are `num0=6` paths that have `H` in the first location \nWe are looking for `k=4`, so having `H` in the first step will lead us to the correct path\nNow, `path = H _ _ _ _; H=2, V=2, k=4`\n\n\nState: `H=2, V=2, k=4`\nLet\'s try adding `H` as the first step, `path_tmp = H H _ _ _`\nIf we fix this, number of valid paths that have `H` in the first location = `nCk(H+V-1, max(H-1,V))  = nCk(3, max(1,2)) = nCk(3,2) = 3`\nWhich means there are `num0=3` paths that have `H H` in the first two locations \nWe are looking for `k=4`, so having `H` in the first step will **NOT** lead us to the correct path\nSo let\'s add `V` instead - `path = H V _ _ _`\nAlso update `k` because after inserting a `V`, we have already ignored the first `num0=3` paths in lexicographical order\nNow, `path = H V _ _ _; H=2, V=1, k=1`\n\nState: `H=2, V=1, k=1`\nLet\'s try adding `H` as the first step, `path_tmp = H V H _ _`\nIf we fix this, number of valid paths that have `H` in the first location = `nCk(H+V-1, max(H-1,V))  = nCk(2, max(1,1)) = nCk(2,1) = 2`\nWhich means there are `num0=2` paths that have `H V H _ _` in the first three locations \nWe are looking for `k=1`, so having `H` in the first step will lead us to the correct path\nNow, `path = H V H _ _; H=1, V=1, k=1`\n\nState: `H=1, V=1, k=1`\nLet\'s try adding `H` as the first step, `path_tmp = H V H H _`\nIf we fix this, number of valid paths that have `H` in the first location = `nCk(H+V-1, max(H-1,V))  = nCk(1, max(0,1)) = nCk(2,1) = 1`\nWhich means there are `num0=2` paths that have `H V H H _` in the first three locations \nWe are looking for `k=1`, so having `H` in the first step will lead us to the correct path\nNow, `path = H V H H _; H=0, V=1, k=1`\n\n\nState: `H=0, V=1, k=1`\nThis case is easy because only `V` is a valid choice since no `H`-s are left \nFinal path found by algo: ` H V H H V`\n\nCode:\n```\nclass Solution {\npublic:\n    unordered_map<int, long long> fact_cache;\n    unordered_map<string, long long> nck_cache; \n    long long factorial(long long x) {\n        if (fact_cache.count(x)) return fact_cache[x];\n        long long res = 1;\n        \n        if (x > 0) res = (long long) x * factorial(x-1);\n        \n        fact_cache[x] = res;\n        return res;\n    }\n    \n    int nCk(int n, int k) {\n        // long long den = factorial(k) * factorial(n-k);\n        // long long num = factorial(n);\n        \n        string key = to_string(n) + "C" + to_string(k);\n        if (nck_cache.count(key)) return nck_cache[key];\n        long long den = factorial(min(k,n-k));\n        long long num = 1;\n        for (long long nn = n; nn > (long long) max(n-k,k); --nn) {\n            num *= nn;\n        }\n        int res = (int) (num/den);\n        nck_cache[key] = res;\n        \n        \n        return res;\n    }\n    \n    string kthSmallestPath(vector<int>& destination, int k) {\n        int V = destination[0], H = destination[1];\n        int n = H + V;\n        vector<char> order({\'H\', \'V\'});\n        string path = "";\n        \n        for (int i = 0; i < n; ++i) {\n            if (!H) {\n                --V;\n                path.push_back(\'V\');\n            }\n            else if (!V) {\n                --H;\n                path.push_back(\'H\');\n            }\n            else {\n                // if 0 placed in place i\n                int num0 = nCk(V+H-1, max(V,H-1));\n                // cout << k << " " << H << " " << V << " " << n-i-1 << "C" << max(H-1,V) << " " << num0 << endl;\n\n                if (num0+1 > k) {\n                    --H;\n                    path.push_back(order[0]);\n                }\n                else {\n                    k -= num0;\n                    --V;\n                    path.push_back(order[1]);\n                }\n            }\n        }\n    \n        return path;\n    }\n};\n```
['Probability and Statistics']