Try possible k
The smallest element in nums must be in the lower array. If we sort the array, our k can be (nums[i] - nums[0]) / 2.\n\nFor each such k, we try to match all pai
The smallest element in `nums` must be in the lower array. If we sort the array, our `k` can be `(nums[i] - nums[0]) / 2`.\n\nFor each such `k`, we try to match all pairs, going from smallest to larger and removing pairs. If we match all pairs, we return the original array.\n\n**C++**\n```cpp\nvector<int> recoverArray(vector<int>& nums) {\n    multiset<int> s(begin(nums), end(nums));\n    int start = *begin(s);\n    for (auto it = next(begin(s)); it != end(s); ++it) {\n        int k = (*it - start) / 2;\n        if (k > 0 && start + 2 * k == *it) {\n            vector<int> res;\n            auto ss = s;\n            while(!ss.empty()) {\n                auto it_h = ss.find(*begin(ss) + 2 * k);\n                if (it_h == end(ss))\n                    break;\n                res.push_back(*begin(ss) + k);\n                ss.erase(begin(ss));\n                ss.erase(it_h);\n            }\n            if (ss.empty())\n                return res;\n        }\n    }\n    return {};\n}\n```
[]