Try all possible k values
Intuition\nBrute force try all possible k values, don\'t try impossible solutions or duplicates.\n\n# Approach\nFirst get all the potential k values for the fir
# Intuition\nBrute force try all possible k values, don\'t try impossible solutions or duplicates.\n\n# Approach\nFirst get all the potential k values for the first entry in the array, one of them must be the right one.\n\nNext try to eliminate the pairs of values from the input corresponding to x - k, x + k recording x as you go. If all the values were eliminated, that\'s a solution.\n\n# Complexity\n- Time complexity:\n$$O(n^2)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nfunc copyMap(orig map[int]int) map[int]int {\n    copy := make(map[int]int, len(orig))\n\n\tfor key, value := range orig {\n\t\tcopy[key] = value\n\t}\n    return copy\n}\n\nfunc decrement(lookup map[int]int, key int) {\n    if _, ok := lookup[key]; ok {\n        lookup[key]--\n        if lookup[key] == 0 {\n            delete(lookup, key)\n        }\n    }\n\n}\n\nfunc recoverArray(nums []int) []int {\n    sort.Ints(nums)\n    sampleSpace := make(map[int]struct{}, len(nums) - 1)\n    lookup := make(map[int]int, len(nums))\n    lookup[nums[0]] = 1\n    for i := 1; i < len(nums); i++ {\n        if _, ok := lookup[nums[i]]; !ok {\n            lookup[nums[i]] = 0\n        }\n        lookup[nums[i]]++\n        diff := int(math.Abs(float64(nums[i] - nums[0])))\n        if diff % 2 == 0 && diff != 0 {\n            sampleSpace[diff / 2] = struct{}{}\n        }\n    }\n\n    for k, _ := range sampleSpace {\n        lookupCopy := copyMap(lookup)\n        candidate := []int{}\n        for _, num := range nums {\n            if _, ok := lookupCopy[num]; !ok {\n                continue\n            }\n            val := num + k * 2\n            decrement(lookupCopy, num)\n            if _, ok := lookupCopy[val]; ok {\n                candidate = append(candidate, val - k)\n                decrement(lookupCopy, val)\n            } else {\n                break\n            }\n        }\n        if len(lookupCopy) == 0 {\n            return candidate\n        }\n    }\n\n    return []int{}\n}\n```
['Go']