Java backtrack solution with optimizations
The idea is a simple backtracking approach, but with optimizations to avoid unnecessary computations.\nThere are two optimizations used in the method backtrack:
The idea is a simple backtracking approach, but with optimizations to avoid unnecessary computations.\nThere are two optimizations used in the method **backtrack**:\n* using a set of **visited** sets, that is sets that have already been considered in this backtracking phase. If there are two sets that are the same it\'s no use considering adding the current element to both of them, because the two resulting backtracking trees are going to be the same anyway.\n* stopping backtracking when we see that the current solution (accumulated in **acc**) is bigger than the best solution so far.\n\n```\nclass Solution {\n    private int min = Integer.MAX_VALUE;\n    private int bucketSize = 0;\n    \n    public int minimumIncompatibility(int[] nums, int k) {\n        int n = nums.length;\n        bucketSize = n / k;\n        \n        List<Set<Integer>> sets = new ArrayList<>();\n        for (int i = 0; i < k; i++) {\n            sets.add(new HashSet<>());\n        }\n        \n        backtrack(nums, 0, sets, 0);\n        \n        return min == Integer.MAX_VALUE ? -1 : min;\n    }\n    \n    private void backtrack(int[] nums, int idx, List<Set<Integer>> sets, int acc) {\n        if (idx >= nums.length) {\n            min = Math.min(min, acc);\n            return;\n        }\n        \n        Set<Set<Integer>> visited = new HashSet<>();\n        \n        for (Set<Integer> set: sets) {\n            if (set.contains(nums[idx]) || set.size() == bucketSize || visited.contains(set)) continue;\n            int impact = computeImpact(set, nums[idx]);\n            acc += impact;\n            if (acc < min) {\n                set.add(nums[idx]);\n                backtrack(nums, idx+1, sets, acc);\n                set.remove(nums[idx]);\n            }\n            acc -= impact;\n            visited.add(set);\n        }\n    }\n    \n    private int computeImpact(Set<Integer> set, int num) {\n        if (set.size() == 0) return 0;\n        if (set.size() == 1) return Math.abs(num - set.iterator().next());\n        int lo = Integer.MAX_VALUE;\n        int hi = Integer.MIN_VALUE;\n        \n        for (int x: set) {\n            lo = Math.min(lo, x);\n            hi = Math.max(hi, x);\n        }\n        \n        if (num < lo) return lo - num;\n        if (num > hi) return num - hi;\n        return 0;\n    }\n}\n```
[]