C++ sort + 2 pointers beats 100%
find all possible k\n2. sort nums\n3. iterate all possible k and use two pointers to check if it works\n\nTC : O(n^2)\nSC : O(n)\n\nclass Solution {\npublic:\n 
1. find all possible `k`\n2. sort `nums`\n3. iterate all possible `k` and use two pointers to check if it works\n\nTC : O(n^2)\nSC : O(n)\n```\nclass Solution {\npublic:\n    vector<int> recoverArray(vector<int>& nums) {\n        int n = nums.size();\n\t\t// find all possible k\n        unordered_set<long> ks;\n        for (int i = 1; i < n; i++) {\n            long sum = nums[i]+nums[0];\n            if (!(sum&1))\n                ks.insert(max(nums[0], nums[i])-(sum>>1));\n        }\n        sort(nums.begin(), nums.end());\n        \n\t\t// iterate all possible k and use two pointers to check if it works\n        vector<int> ans;\n        for (auto k : ks) {\n            if (!k) continue;\n            \n            long k2 = k<<1;\n\t\t\t// find the start position of upper to nums[0]\n            int upperi = lower_bound(nums.begin(), nums.end(), nums[0]+k2) - nums.begin();\n            if (upperi == n || nums[upperi] != nums[0]+k2) continue; // no such upper\n            \n            bool used[2000] = {};\n            used[0] = used[upperi++] = true;\n            ans.push_back(nums[0]+k);\n            \n            for (int loweri = 1; upperi < n; loweri++) {\n                if (used[loweri]) continue;\n                \n                long upper = nums[loweri]+k2;\n                while (upperi < n && (upper > nums[upperi] || used[upperi])) upperi++;\n                \n                if (upperi == n || upper != nums[upperi]) break;\n                    \n                used[upperi++] = true;\n                ans.push_back(nums[loweri]+k);\n            }\n            \n            if (ans.size() == (n>>1)) break;\n            \n            ans.clear();\n        }\n        return ans;\n    }\n};\n```
[]