Swift top down Bitmask DP - O(n^2*2^n)
\tclass Solution {\n\t\tvar arr: [Int]!, n = 0, size = 0, total = 0, starts: [Int]!\n\t\tvar dp = [[[Int]]]\n\t\tlet inf = 10000000000\n\n\t\tfunc minimumIncomp
\tclass Solution {\n\t\tvar arr: [Int]!, n = 0, size = 0, total = 0, starts: [Int]!\n\t\tvar dp = [[[[Int]]]](repeating:\n\t\t\t\t\t\t\t\t[[[Int]]](repeating:\n\t\t\t\t\t\t\t\t\t\t\t[[Int]] (repeating:\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t[Int](repeating: -1, count: 17),\n\t\t\t\t\t\t\t\t\t\t\t\t\t count: 8),\n\t\t\t\t\t\t\t\t\t\t  count: 1<<16),\n\t\t\t\t\t\t\t count: 16)\n\t\tlet inf = 10000000000\n\n\t\tfunc minimumIncompatibility(_ nums: [Int], _ k: Int) -> Int {\n\t\t\tguard k != 1 else {\n\t\t\t\tlet set = Set(nums)\n\t\t\t\tif set.count == nums.count {\n\t\t\t\t\treturn nums.max()!-nums.min()!\n\t\t\t\t}\n\t\t\t\treturn -1\n\t\t\t}\n\t\t\tguard nums.count != k else {\n\t\t\t\treturn 0\n\t\t\t}\n\t\t\tarr = nums.sorted()\n\t\t\tstarts = [0] + arr\n\t\t\tn = arr.count\n\t\t\ttotal = (1<<n)-1\n\t\t\tsize = n/k\n\n\t\t\tlet res = dfs(0,0,0,0)\n\t\t\treturn res == inf ? -1 : res\n\t\t}\n\n\t\t/**\n\t\t cur is the element we need to start scanning from\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t  01234567\n\t\t mask is used to track which elemnents are used, e.g. 01100011 means 1st, 2nd, 6th and 7th elements are used\n\t\t gsize tracks the size of this group, each group is arr.count/k elements\n\t\t start tracks the starting point of this group, it\'s used to find the min element of this group, since we are sorting the array, starting point is minimum element. It\'s 1-based index. so if array size is n, start will go from, 1 to n instead of 0 to n-1.\n\t\t */\n\t\tfunc dfs(_ cur: Int,\n\t\t\t\t _ mask: Int,\n\t\t\t\t _ gsize: Int,\n\t\t\t\t _ start: Int) -> Int {\n\n\t\t\tif mask == total {\n\t\t\t\treturn 0\n\t\t\t}\n\n\t\t\tguard dp[cur][mask][gsize][start] == -1 else {\n\t\t\t\treturn dp[cur][mask][gsize][start]\n\t\t\t}\n\n\t\t\tvar res = inf\n\n\t\t\t// start = 0 means this is a new group\n\t\t\tif start == 0 {\n\t\t\t\tvar i = 0, j = 0\n\t\t\t\t//for new group we first find the first element in the group\n\t\t\t\twhile i < n {\n\t\t\t\t\tj = 1<<i\n\t\t\t\t\tguard j&mask == 0 else {\n\t\t\t\t\t\ti += 1\n\t\t\t\t\t\tcontinue\n\t\t\t\t\t}\n\t\t\t\t\tbreak\n\t\t\t\t}\n\t\t\t\tlet mc = mask|j\n\n\t\t\t\tfor k in stride(from: i+1, to: n, by: 1) {\n\t\t\t\t\t//find next eligible element\n\t\t\t\t\tguard arr[i] != arr[k] else {\n\t\t\t\t\t\tcontinue\n\t\t\t\t\t}\n\t\t\t\t\t//start array is 1 based so we add 1 to i\n\t\t\t\t\tres = min(res, dfs(k, mc, 1, i + 1))\n\t\t\t\t}\n\t\t\t} else {\n\t\t\t\tfor i in stride(from: cur, to: n, by: 1) {\n\t\t\t\t\tlet j = 1<<i\n\t\t\t\t\tguard mask&j == 0 else {\n\t\t\t\t\t\tcontinue\n\t\t\t\t\t}\n\t\t\t\t\t// if this is the last item in the group, we need to finx max-min and add it to result\n\t\t\t\t\tif gsize == size-1 {\n\t\t\t\t\t\tlet mn = starts[start]\n\t\t\t\t\t\tlet mx = arr[i]\n\t\t\t\t\t\t//because this group has ended, next cur will start from 0, next group size will be 0 and start will be unavailable (0 means unavailable and start array is 1 based)\n\t\t\t\t\t\tres = min(res, mx-mn + dfs(0, mask|j, 0, 0))\n\t\t\t\t\t} else {\n\t\t\t\t\t\tvar next = i+1\n\t\t\t\t\t\twhile next < n && (arr[i] == arr[next]) {\n\t\t\t\t\t\t\tnext += 1\n\t\t\t\t\t\t}\n\t\t\t\t\t\t//find next item in group\n\t\t\t\t\t\tif next < n {\n\t\t\t\t\t\t\tres = min(res, dfs(next, mask|j, gsize + 1, start))\n\t\t\t\t\t\t}\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t\tdp[cur][mask][gsize][start] = res\n\n\t\t\treturn res\n\t\t}\n\t}\n
['Dynamic Programming', 'Swift', 'Bitmask']