Set a limitation and other tips (812 ms in Python3)
\nThe fastest solution till now seem like a priority queue(PQ)\nwhile there is still a little step to optimize.\n\nOne of that could be find a approximate downb
\nThe fastest solution till now seem like a priority queue(PQ)\nwhile there is still a little step to optimize.\n\nOne of that could be find a approximate downbound value.\nWith that value, some of the sum will be filtered out, so it maintain a smaller priority queue, in this way, it will cost less to maitain the PQ.\n\nWhile the important thing is how to find that value with less effort.\n\nFirst lets pick x biggest numbers, these numbers could give 2 ** x count of sums , in the other words, \nthere is 2**x sums are large enough to tell how the downbound value could be.\nThat will be the sum of the x nums.\n\n```\nx = ceil(log(k) / log(2))\n```\n\nAnd hereby, the final code include three optimizes based on a python PQ solution.\n\n\n```\nclass Solution:\n    def kSum(self, nums: List[int], k: int) -> int: \n        m = sum(x for x in nums if x > 0)\n        vals = sorted(abs(x) for x in nums if x)\n        k = (k - 1) // (2 ** (len(nums) - len(vals))) + 1\n        k1 = 2 ** len(vals) + 1 - k\n        reverse = k > k1\n        if reverse:\n            k = k1\n            m = sum(vals) - m\n        pq = [(-m, 0)] # priority queue \n        lim = -m + sum(vals[: ceil(log(k) / log(2))])\n        for _ in range(k): \n            x, i = heappop(pq)\n            if i < len(vals): \n                if x+vals[i] <= lim:\n                    heappush(pq, (x+vals[i], i+1))\n                if i : heappush(pq, (x-vals[i-1]+vals[i], i+1))\n        return x if reverse else -x\n     \n   ```\n\n\nReference from my submissions:\noptimize a little bit more\n08/26/2022 09:42\tAccepted\t812 ms\t28.3 MB\tpython3\n\noptimize by less check approximate bound based on the submitted fastest solution\n08/26/2022 00:53\tAccepted\t1034 ms\t29.8 MB\tpython3\n\noptimize by check approximate bound based on the submitted fastest solution\n08/26/2022 00:53\tAccepted\t1548 ms\t28.4 MB\tpython3\n\noptimize by remove zeros based on the submitted fastest solution\n08/26/2022 00:34\tAccepted\t1187 ms\t28.1 MB\tpython3\n\ncopy of submitted fastest solution\n08/26/2022 00:27\tAccepted\t1437 ms\t29 MB\tpython3\n\nMy silly solution\n08/26/2022 00:24\tAccepted\t9533 ms\t479.1 MB\tpython3\n\n\n\n\n
[]