[Golang] DP with explanation O(2^n * n^2)
For one group of selected numbers with size k, incompatibility is determined and order doesn\'t matter, also remaining numbers need to keep selecting size k num
For one group of selected numbers with size k, incompatibility is determined and order doesn\'t matter, also remaining numbers need to keep selecting size k numbers, which means it\'s a recursion.\n\n```\ne.g. nums = [1, 2, 3, 4, 5, 6], k = 2\nif selected = [2, 5], incompatibility = 5 - 2 = 3\nif selected = [5, 2], incompatibility = 5 - 2 = 3\nit means order of selection doens\'t change incompatibility value.\n\nremaining nums = [1, 3, 4, 6], keep selecting size = 2 numbers until no numbers can be selected.\n```\n\nSelect k size numbers and order doesn\'t matter means to find combinations of numbers.\n\nTo denote some numbers are selected disrescarding order, bitmask can be used.\n\nTime complexity for this is similar to traveling salseman problem (TSP). There are n numbers to start, total 2^n combinations, for each route is determined takes n to find incompatibility value, overall time complexity is O(2^n * n^2).\n\n```\ne.g. nums = [1, 2, 3, 4, 5, 6], k = 2\n  bitmask = [0  0  0  0  0  0] means no number is selected\n\nselect numbers = [2, 5], bitmask = [0  1  0  0  1  0]\nselect numbers = [5, 2], bitmask = [0  1  0  0  1  0]\n\nso if selected numbers are same with different order, bitmask gets same value which can be used to check if group of numbers are selected or not\n```\n\nOverall algorithm is to find valid combination of number with size equals to k, iterate through all of combinations, find incompatibiity value and keep select remaing numbers for size equals to k.\n\n```golang\nfunc minimumIncompatibility(nums []int, k int) int {\n\tsize := len(nums)\n\tif size == k {\n\t\treturn 0\n\t}\n\n\t// make sure no number appear more than k times\n\tcounter := make(map[int]int)\n\tfor _, n := range nums {\n\t\tcounter[n]++\n\t\tif counter[n] > k {\n\t\t\treturn -1\n\t\t}\n\t}\n\n\tmaxMask := (1 << size) - 1\n\tused := make(map[int]int)\n\n\tval := dfs(nums, 0, maxMask, size/k, used)\n\tif val >= 9999 {\n\t\treturn -1\n\t}\n\n\treturn val\n}\n\nfunc dfs(nums []int, currentMask, maxMask, groupSize int, used map[int]int) int {\n\tif currentMask == maxMask {\n\t\treturn 0\n\t}\n\n\t// used already computed value\n\tif val, ok := used[currentMask]; ok {\n\t\treturn val\n\t}\n\n\t// find unique unused numbers\n\tuniq := make(map[int]bool)\n\tavailable := make([]int, 0)\n\tsize := len(nums)\n\tfor i := 0; i < size; i++ {\n\t\tif (1<<(size-1-i))&currentMask > 0 || uniq[nums[i]] {\n\t\t\tcontinue\n\t\t}\n\t\tuniq[nums[i]] = true\n\n\t\tavailable = append(available, i)\n\t}\n\n\t// insufficient to form a group\n\tif len(available) < groupSize {\n\t\treturn 9999\n\t}\n\n\t// generate combinations from those numbers\n\tcombs := findCombinations(available, groupSize)\n\n\t// count value\n\tincompatibility := 9999\n\tfor _, c := range combs {\n\t\tnextMask := currentMask\n\t\tmaxVal, minVal := math.MinInt32, math.MaxInt32\n\n\t\tfor _, j := range c {\n\t\t\tmaxVal = max(maxVal, nums[j])\n\t\t\tminVal = min(minVal, nums[j])\n\t\t\tnextMask |= 1 << (size - 1 - j)\n\t\t}\n\n\t\tincompatibility = min(incompatibility, maxVal-minVal+dfs(nums, nextMask, maxMask, groupSize, used))\n\t}\n\tused[currentMask] = incompatibility\n\n\treturn incompatibility\n}\n\ntype Comb struct {\n\tIdx  int\n\tData []int\n}\n\n// BFS\nfunc findCombinations(available []int, groupSize int) [][]int {\n\tans := make([][]int, 0)\n\tstack := []Comb{\n\t\t{0, []int{}},\n\t}\n\tsize := len(available)\n\n\tfor len(stack) > 0 {\n\t\ts := stack[len(stack)-1]\n\t\tstack = stack[:len(stack)-1]\n\t\tidx, data := s.Idx, s.Data\n\n\t\tif len(data) == groupSize {\n\t\t\tans = append(ans, data)\n\t\t\tcontinue\n\t\t}\n\n\t\tfor ; idx < size; idx++ {\n\t\t\tlength := len(data)\n\t\t\ttmp := make([]int, length, length+1)\n\t\t\tcopy(tmp, data)\n\t\t\ttmp = append(tmp, available[idx])\n\t\t\tstack = append(stack, Comb{\n\t\t\t\tIdx:  idx + 1,\n\t\t\t\tData: tmp,\n\t\t\t})\n\t\t}\n\t}\n\n\treturn ans\n}\n\nfunc max(i, j int) int {\n\tif i >= j {\n\t\treturn i\n\t}\n\treturn j\n}\n\nfunc min(i, j int) int {\n\tif i <= j {\n\t\treturn i\n\t}\n\treturn j\n}\n```
['Dynamic Programming', 'Go']