C++ Combination
See my latest update in repo LeetCode\n\n## Solution 1. Combination\n\nGiven destination: (row, column), we will have column H and row V in the result.\n\nLet\'
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1. Combination\n\nGiven `destination: (row, column)`, we will have `column` `H` and `row` `V` in the result.\n\nLet\'s denote `h = column`, `v = row` meaning the number of `H` and `V` left to pick, respectively. The result is of length `h + v`.\n\nWe pick the character one by one for the result.\n\nFor the first character, if we pick `H`, the rest of characters can form `c = nCr(h - 1 + v, v)` combinations.\n\nIf `k <= c`, it means that the result is one of these `c` combinations. So we should pick `H` here. We append `H` to the result and `--h`.\n\nOtherwise, we should pick `V` instead, and do `--v` and `k -= c` (skip these `c` combinations).\n\nWe keep doing this until we made choice for all the `h + v` characters.\n\n```cpp\n// OJ: https://leetcode.com/contest/weekly-contest-213/problems/kth-smallest-instructions/\n// Author: github.com/lzl124631x\n// Time: O((H + V)^2)\n// Space: O(1)\nclass Solution {\n    int comb(int n, int r) {\n        long ans = 1;\n        for (int i = 1, j = n - r + 1; i <= r; ++i, ++j) ans = ans * j / i;\n        return ans;\n    }\npublic:\n    string kthSmallestPath(vector<int>& A, int k) {\n        int h = A[1], v = A[0], N = h + v;\n        string s;\n        for (int i = 0; i < N; ++i) {\n            if (h) { // we have H available to pick\n                int c = comb(h - 1 + v, v); // if we pick H at the current position, there will be `c` combinations for the rest of characters\n                if (k <= c) { // k is covered within `c`, so we should pick H.\n                    s += \'H\';\n                    --h;\n                } else { // otherwise we should pick V\n                    k -= c;\n                    s += \'V\';\n                    --v;\n                }\n            } else { // no H left, have to pick V.\n                s += \'V\';\n                --v;\n            }\n        }\n        return s;\n    }\n};\n```\n\n---\n\nUpdate 11/1/2020:\n\nWhy `k -= c`?\n\nExample:\n\nAssume `k = 4` and we have `2H2V` to pick.\n\nIf the first character is `H`, then there are `1H2V` left which can form `nCr(3, 2) = 3` combinations.\n\n```\nH HVV\nH VHV\nH VVH\n\nV HHV   <\nV HVH\nV VHH\n```\n\nBut since `k = 4 > 3` so the first character must not be `H`. So `V` is selected. \n\nNow we have `2H1V` left. It is `k\' = 4 - 3 = 1`st string that we are looking for now.
[]