C++ Very Easy Solution
Approach\n\nThe idea is very simple, we know the minimum element in the permutation belongs to lower and maximum element belongs to higher. So , we\'ll push min
## Approach\n\nThe idea is very simple, we know the minimum element in the permutation belongs to lower and maximum element belongs to higher. So , we\'ll push minimum element in our ans array, then for each remaining element we\'ll try it to make first element of b and find k as\n\n\t\t\t\t\t\t\t\thigher[i] - lower[i] = arr[i] + k - (arr[i] - k) = 2*k\n\nusing this we can find possible values of k and check if we can form the array using this value of k.\n\n\n## Code\n\n```\nvector<int> recoverArray(vector<int>& nums) {\n        \n\t\t//sorting the nums array\n        sort(nums.begin(),nums.end());\n        \n\t\t//we\'ll try every nums[i] as first element of higher array excpet nums[0]\n\t\t//as it is first element of lower\n        for(int i=1;i<size(nums);i++)\n        {\n            vector<int> a;\n\t\t\t//pushing minimum element in lowest\n            a.push_back(nums[0]);\n\t\t\t\n\t\t\t//calculating k after assuming nums[i] as first element of higher\n            int k = nums[i] - a.back();\n            \n\t\t\t//in case k is odd or k = 0, skip !\n            if(k&1 || k == 0) continue;\n            \n            multiset<int> st(nums.begin(),nums.end());\n\t\t\t\n\t\t\t//delete used elements ,ie, nums[0] and nums[i]\n            st.erase(st.find(a.back())) , st.erase(st.find(nums[i]));\n\t\t\t\n            while(!st.empty())\n            {\n                // now current minimum value will be part of lower array, so pushing it to a\n\t\t\t\t// and deleting from multiset\n                a.push_back(*st.begin());\n                st.erase(st.begin());\n\t\t\t\t\n\t\t\t\t//now corresponding element in higher should be\n\t\t\t\t// last pushed element in lower + current k\n                auto it = st.find(a.back() + k);\n\t\t\t\t\n\t\t\t\t//if we cann\'t find corresponding element in higher, we\'ll break the loop\n                if(it == st.end()) break;\n\t\t\t\t\n\t\t\t\t//else delete it from multiset\n                st.erase(it);\n            }\n            \n\t\t\t//now if our multiset is empty, ie , we have used all the elements then\n\t\t\t// it is clear that current value of k is the right choice\n\t\t\t// increment every value of lower by k/2 as higher[i] - lower[i] = 2*k\n\t\t\t// and we need to add k to lower[i] to make current array\n            if(st.empty())\n            {\n                for(auto &val : a) val += k/2;\n                // cout<<"\\n";\n                return a;\n            }\n            \n        }\n        \n        assert(false);\n        \n    }\n```\n\n**Time Complexity :** O(nlogn + n^2)
['C']