sorting + greedy + hashmap
the smallest number could pair with any number strictly larger than it so long as their difference is even, since n<=1000, we can enumerate them in one pass\n\n
the smallest number could pair with any number strictly larger than it so long as their difference is even, since n<=1000, we can enumerate them in one pass\n\nthen for every possible k stored, see if it is possible to pair all numbers with it. that is, go through the nums, see if there is any a - 2*k before it, if yes, both of them are paired, remove the previous one and do not record the current one -- and of course we append a-k to the list of possible original list with current k. otherwise store the corrent one as unpaired. when no number is left after the loop, this k is a plausible solution and we return the original array we have recorded.\n\n# Code\n```\nclass Solution:\n    def recoverArray(self, nums: List[int]) -> List[int]:\n        nums.sort()\n        maxk = (nums[-1] - nums[0]) // 2\n        n = len(nums)\n        possiblek = set([])\n        for i in range(1,n):\n            if nums[i]!=nums[0] and (nums[i] - nums[0]) % 2 == 0 and (nums[i] - nums[0]) // 2 <= maxk:\n                possiblek.add((nums[i] - nums[0]) // 2) \n        for k in possiblek:\n            seen = {}\n            res = []\n            for a in nums:\n                if a - 2*k in seen:\n                    seen[a - 2*k] -= 1\n                    if seen[a - 2*k] == 0:\n                        del seen[a - 2*k]\n                    res.append(a-k)\n                else:\n                    if a not in seen:\n                        seen[a] = 0\n                    seen[a] += 1\n            if not seen: return res\n\n\n\n        \n```
['Hash Table', 'Greedy', 'Sorting', 'Python3']