<p>You are given an integer array <code>nums</code>​​​ and an integer <code>k</code>. You are asked to distribute this array into <code>k</code> subsets of <strong>equal size</strong> such that there are no two equal elements in the same subset.</p>

<p>A subset&#39;s <strong>incompatibility</strong> is the difference between the maximum and minimum elements in that array.</p>

<p>Return <em>the <strong>minimum possible sum of incompatibilities</strong> of the </em><code>k</code> <em>subsets after distributing the array optimally, or return </em><code>-1</code><em> if it is not possible.</em></p>

<p>A subset is a group integers that appear in the array with no particular order.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,1,4], k = 2
<strong>Output:</strong> 4
<strong>Explanation:</strong> The optimal distribution of subsets is [1,2] and [1,4].
The incompatibility is (2-1) + (4-1) = 4.
Note that [1,1] and [2,4] would result in a smaller sum, but the first subset contains 2 equal elements.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [6,3,8,1,3,1,2,2], k = 4
<strong>Output:</strong> 6
<strong>Explanation:</strong> The optimal distribution of subsets is [1,2], [2,3], [6,8], and [1,3].
The incompatibility is (2-1) + (3-2) + (8-6) + (3-1) = 6.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,3,3,6,3,3], k = 3
<strong>Output:</strong> -1
<strong>Explanation:</strong> It is impossible to distribute nums into 3 subsets where no two elements are equal in the same subset.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 16</code></li>
	<li><code>nums.length</code> is divisible by <code>k</code></li>
	<li><code>1 &lt;= nums[i] &lt;= nums.length</code></li>
</ul>

class Solution {
public:
    const int MAX = 1e9 + 7;
    int solve(std::vector<int> &nums, int n, int k, int mask, int target,
              std::vector<int> &incompatibility,
              std::vector<int> &dpTable) {
                
        if (mask == 0) return 0;

        if (dpTable[mask] != -1) return dpTable[mask];

        int result = MAX;
        for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
            if (__builtin_popcount(submask) % target == 0 && incompatibility[submask] > 0) {
                result = std::min(result, incompatibility[submask] + solve(nums, n, k - 1, mask ^ submask, target, incompatibility, dpTable));
            }
        }

        return dpTable[mask] = result;
    }

    void prepare(std::vector<int> &nums, int n, int target, std::vector<int> &vec) {
        std::vector<int> freq(n + 1, 0);

        for (int submask = 0; submask < (1 << n); ++submask) {
            bool isValid = true;
            int maxValue = INT_MIN, minValue = INT_MAX;
            freq.assign(n + 1, 0);
            // number of 1s reach target count
            if (__builtin_popcount(submask) == target) {
                // check:
                for (int i = 0; i < n; ++i) {
                    if (submask & (1 << i)) {
                        freq[nums[i]]++;
                    }
                }

                for (int j = 1; j <= n; ++j) {
                    if (freq[j] > 1) {
                        isValid = false;
                        break;
                    }
                }
                if (isValid) {
                    for (int j = 1; j <= n; ++j) {
                        if (freq[j] > 0) {
                            minValue = std::min(minValue, j);
                            maxValue = std::max(maxValue, j);
                        }
                    }
                    vec[submask] = maxValue - minValue;
                }

                for (int i = 0; i < n; ++i) {
                    if (submask & (1 << i)) {
                        freq[nums[i]]--;
                    }
                }
            }
        }
    }

    int minimumIncompatibility(vector<int>& nums, int k) {
        int n = static_cast<int>(nums.size());

        if (k == 1) {
            std::set<int> numSet(nums.begin(), nums.end());
            if (numSet.size() < nums.size()) {
                // has duplicated numbers
                return -1;
            }
            return *numSet.rbegin() - *numSet.begin();
        }
        if (k == n) {
            return 0;
        }

        std::vector<int> incompatibility(1 << n, -1);
        prepare(nums, n, n / k, incompatibility);

        // Top-Down
        std::vector<int> dpTable(1 << n, -1);
        int result = solve(nums, n, k, (1 << n) - 1, n / k, incompatibility, dpTable);

        return result == MAX ? -1 : result;

        // std::vector<int> dpTable(1 << n, -1);
        // dpTable[0] = 0;
        // for (int mask = 0; mask < (1 << n); ++mask) {
        //     if (__builtin_popcount(mask) % (n / k) == 0) {
        //         for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
        //             // if current submask is valid, the rest of mask (submask ^ mask) already has valid value
        //             if (incompatibility[submask] != -1 && dpTable[submask ^ mask] != -1) {
        //                 if (dpTable[mask] == -1) {
        //                     dpTable[mask] = incompatibility[submask] + dpTable[submask ^ mask];
        //                 }
        //                 else {
        //                     dpTable[mask] = std::min(dpTable[mask],
        //                                              incompatibility[submask] + dpTable[submask ^ mask]);
        //                 }
        //             }
        //         }
        //     }
        // }
        // return dpTable[(1 << n) - 1];
    }
};
14900