Recursive Combinatorics 99% runtime
Intuition\nWe might be tempted to brute force enumerate all strings then sort and get the top K. But, a quick calculation shows that if we naively enumerate eve
# Intuition\nWe might be tempted to brute force enumerate all strings then sort and get the top K. But, a quick calculation shows that if we naively enumerate even the top K strings, it is too much (nCr)\n\nThis motivates us to find a more guided approach towards finding the best string. The key insight is found by playing with strings: if we place a certain letter (V/H), how many completed strings will start with said letter?\n\nFor example, if we have a string of length 1, H, then: (r+c-1)C(c-1) strings will start with this starting string. Not only that, we know that all (r+c-1)C(c-1) go before any string that starts with V. This means if k <= (r+c-1)C(c-1), it must be true that our answer starts with H! \n\nWe can repeat this process recursively, choosing to add "H" or "V" based on whether our target string k lies within the set of strings beginning with each letter. Eventually, we can narrow down and get our answer.\n\n# Code\n```\nfrom math import comb\nclass Solution:\n    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n        def rec(r,c,kp): \n            if kp <= 1 and (r == 0 or c == 0):\n                a = ""\n                if r > 0:\n                    a = "V"*r\n                elif c > 0:\n                    a = "H"*c\n                return a\n            a = ""\n            if c > 0:\n                lower = comb(r+c-1,c-1) # say we take a column away\n                if lower >= kp:\n                    a += "H" + rec(r,c-1,kp)\n                else:\n                    a += "V" + rec(r-1,c,kp-lower)\n            else: # everything is either a row or done\n                a += rec(r-1,c,kp) + "V"\n\n            return a\n        return rec(destination[0], destination[1], k)\n```
['Python3']