Backtracking + Optimization Using TreeSet/LinkedHashSet
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- The problem aims to partition the array into k subsets of equal size, minimizing the sum of differences between the maximum and minimum elements in each subset (incompatibility).\n- Use backtracking with LinkedHashSet[] to explore all subset partitions, ensuring no duplicate numbers within a subset and that the subset size equals nums.length/k.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1) Sort nums to simplify pruning invalid subsets.\n2) Use LinkedHashSet[] lookup to track elements in each subset (preserves insertion order).\n3) At each index, try placing nums[i] in all subsets:\n4) Skip subsets that already contain nums[i] or are full.\n5) Calculate the incompatibility for a complete partition:\nTraverse each subset to compute the difference between the first and last elements.\n6) Recursively backtrack to explore all valid configurations.\n\n# Code\n```java []\n// class Solution {\n// //Handle the case where nums aren\'t 0  \n//     int min = Integer.MAX_VALUE;\n//     public boolean backtrack(int[] nums ,int k,TreeSet<Integer>[] lookup ,int i){\n//         if(i==nums.length){\n//             //find min and max from all array points\n//             int sum = 0;\n//             for(TreeSet set : lookup){\n//                 int last = (int)set.last();\n//                 int first = (int)set.first();\n//                 sum += last - first;\n//             }\n//             min = Math.min(min,sum);\n//             return true;\n//         }\n\n//         //else try adding to all\n//         // boolean added = false;\n//         boolean ans = false;\n//         for(int j=0;j<k;j++){\n//             if(lookup[j].contains(nums[i]) || lookup[j].size()==nums.length/k){\n//                 continue; //skip\n//             }\n//             // if(i!=0 && nums[i] == nums[i-1])\n//             // added= true;\n//             lookup[j].add(nums[i]);\n//             ans |= backtrack(nums,k,lookup,i+1);\n//             lookup[j].remove(nums[i]);\n//             if(lookup[j].isEmpty()) break;\n//         }\n//         return ans;\n//     }\n//     public int minimumIncompatibility(int[] nums, int k) {\n//         // if(nums.length%k!=0) return -1; // already provided\n//         Arrays.sort(nums);\n//         TreeSet<Integer>[] lookup = new TreeSet[k];\n//         int setLength = nums.length/k;\n//         for(int i=0;i<k;i++){\n//             lookup[i] = new TreeSet<Integer>();\n//         }\n//         boolean ans =backtrack(nums,k,lookup,0);\n//         return ans? min : -1;\n//     }\n// }\n\n\n\n//Linked HashSet and Sorting\n//Both work - leetcode ke natak hai\n\n// class Solution {\n// //Handle the case where nums aren\'t 0  \n//     int min = Integer.MAX_VALUE;\n//     public boolean backtrack(int[] nums ,int k,LinkedHashSet<Integer>[] lookup ,int i){\n//         if(i==nums.length){\n//             //find min and max from all array points\n//             int sum = 0;\n//             for(LinkedHashSet<Integer> set : lookup){\n//                 Integer first = null;\n//                 Integer last = null;\n\n//                 for (Integer num : set) {\n//                     if (first == null) {\n//                         first = num;\n//                     }\n//                     last = num;\n//                 }\n//                 sum += last-first;\n//             }\n            \n//             min = Math.min(min,sum);\n//             return true;\n//         }\n\n//         //else try adding to all\n//         // boolean added = false;\n//         boolean ans = false;\n//         for(int j=0;j<k;j++){\n//             if(lookup[j].contains(nums[i]) || lookup[j].size()==nums.length/k){\n//                 continue; //skip\n//             }\n//             // if(i!=0 && nums[i] == nums[i-1])\n//             // added= true;\n//             lookup[j].add(nums[i]);\n//             ans |= backtrack(nums,k,lookup,i+1);\n//             lookup[j].remove(nums[i]);\n//             if(lookup[j].isEmpty()) break;\n//         }\n//         return ans;\n//     }\n//     public int minimumIncompatibility(int[] nums, int k) {\n//         // if(nums.length%k!=0) return -1; // already provided\n//         Arrays.sort(nums);\n//         LinkedHashSet<Integer>[] lookup = new LinkedHashSet[k];\n//         int setLength = nums.length/k;\n//         for(int i=0;i<k;i++){\n//             lookup[i] = new LinkedHashSet<Integer>();\n//         }\n//         boolean ans =backtrack(nums,k,lookup,0);\n//         return ans? min : -1;\n//     }\n// }\n\n\nclass Solution {\n    public int minimumIncompatibility(int[] nums, int k) {\n        Integer[] mem = new Integer[1<<nums.length];\n        int min =  min(nums,k,(1<<nums.length)-1,mem);\n        return min==Integer.MAX_VALUE?-1:min;\n    }\n\n    public int min(int[] nums,int k,int mask,Integer[] mem){\n        if(mask==0)\n            return 0;\n        if(mem[mask]!=null)\n            return mem[mask];\n        int min = Integer.MAX_VALUE;\n        a:\n        for(int sub = mask;sub>0;sub = (sub-1)&mask){\n            if(Integer.bitCount(sub)!=nums.length/k)\n                continue;\n\n            TreeSet<Integer> set = new TreeSet<>();\n            for(int i = 0;i<nums.length;i++){\n                if((sub&(1<<i))>0){\n                    if(!set.add(nums[i]))\n                        continue a;\n\n                }\n            }\n            int next = min(nums,k,mask&(~sub),mem);\n            if(next!=Integer.MAX_VALUE){\n                min = Math.min(min,set.last()-set.first()+next);\n            }\n        }\n        mem[mask] = min;\n        return min;\n    }\n}\n```
['Array', 'Backtracking', 'Java']