[Python] Sort and try every possible k while recover origin on the fly
\nfrom collections import defaultdict\n\nclass Solution:\n    def recoverArray(self, nums: List[int]) -> List[int]:\n        nums.sort()\n        for i in range
```\nfrom collections import defaultdict\n\nclass Solution:\n    def recoverArray(self, nums: List[int]) -> List[int]:\n        nums.sort()\n        for i in range(1, len(nums)):\n\t\t\t# skip the same k or k is odd\n            if nums[i] == nums[i - 1] or (nums[i] - nums[0]) & 1: continue\n            k = (nums[i] - nums[0]) // 2\n            dt = defaultdict(int)\n            cur = [] # cur to store origin\n            for v in nums:\n                if dt[v]:\n                    dt[v] -= 1\n                    cur.append(v - k)\n                else: dt[v + 2 * k] += 1\n            if len(cur) == len(nums) // 2: return cur\n        return []\n```
[]