[Python] Math solution, Introduction to Combinatorics
Feel free to skip to the solution below if you already understand combinatorics.\n\nIntroduction\n"Combinatorics" is basically the mathematical science of count
*Feel free to skip to the solution below if you already understand combinatorics.*\n\n**Introduction**\n"Combinatorics" is basically the mathematical science of counting. In our case, as software engineers, it\'s usually about the efficient automation of that counting - and there\'s a lot of counting to be done here, for sure!\n\nFirst of all, we know these things, regardless of the destination:\n1. Since Bob has to walk from `(0, 0)` to `(r, c)`, he has to follow a total of `r + c` instructions.\n2. `r` of those instructions will be downward (`"V"`) movements, and `c` of the instructions will be horizontal (`"H"`) movements.\n\nSo, we know that every set of instructions for Bob will be some string that is the combination of `"H"` and `"V"` with length `r + c`, exactly `r` characters will be `"V"`, and exactly `c` characters will be `"H"`.\n\n**Combinatorics**\nNow that we have that out of the way, let\'s analyze a hint that the problem gives us. The final constraint says this:\n> `1 <= k <= nCr(row + column, row)`, where `nCr(a, b)` denotes `a` choose `b`.\n\n`nCr(a, b)`, or "`a` choose `b`" as they put it, is the number of ways that you can select `b` elements from a set of `a` unique elements.  Let\'s consider `nCr(3, 2)` for example: that means we have 3 unique elements - `000`. Let `1` represent an element that we\'ve selected: there are three ways to select exactly 2 elements, shown below:\n- `011`\n- `101`\n- `110`\n \nYou don\'t need the formula for `nCr(a, b)` since your language most likely has it as a library, but here it is if you\'re interested (`!` is the [factorial](https://en.wikipedia.org/wiki/Factorial) function):\n> `nCr(a, b) = (a!) / ((b!) * (a - b)!)`\n\n**Solution**\n`"H"` is lexicographically smaller than `"V"`. That means that, at index `i` of an arbitrary solution, placing an `"H"` at `i` will make the resulting instruction set lexicographically smaller than if we placed a `"V"` at that index instead.\n\nLet\'s break this down in terms of what we\'ve learned about Combinatorics. If we have `r + c` total elements and `r` of those elements are `"V"`, then we have `nCr(r + c, r)` possible instruction sets that Bob can walk. At each of his `r + c` total steps, we have two options:\n- Walk right one column, which will leave us with the same number of `"V"`\'s\n- Walk down one row, which will decrease our number of `"V"`\'s by 1 (remember that we only have `r` of these!)\n\n**If we choose to walk down a row when we have N more steps and R possible rows left to walk down (including the current step), then we\'re cutting out the number of combinations of (N - 1) steps with R rows to walk down, because all of those combinations would result in a lexicographically smaller instruction set.**\n\nSo, for each step where we have N more possible steps (including the current step), calculate `nCr(N - 1, R)`. If k is less than or equal to this number, travel horizontally. Otherwise, subtract that number from k, decrease the number of vertical movements we\'re allowed to make, and then travel vertically.\n\n```\ndef kthSmallestPath(self, destination: List[int], k: int) -> str:\n        from math import comb\n        r, c = destination\n        \n        ret = []\n        remDown = r\n        for i in range(r + c):\n            remSteps = r + c - (i + 1)\n            com = comb(remSteps, remDown)\n            if com >= k:\n                ret.append("H")\n            else:\n                remDown -= 1\n                k -= com\n                ret.append("V")\n                \n        return \'\'.join(ret)\n```\n\nPlease leave a comment if you have any questions!
['Math', 'Combinatorics', 'Python']