Can anyone figure out what is the complexity of this code?
Nothing fancy, but just stored the max-min of a subset in cache.\nThe part I do not understand is what is the complexity.\nConsider following test case:\n[1,2,3
Nothing fancy, but just stored the `max-min` of a subset in `cache`.\nThe part I do not understand is what is the complexity.\nConsider following test case:\n[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]\n16\nThe invocation of `solve` on the bottom of stack has a for loop of size `2^n`, although within it only 16 selections are valid.\nOn the 2nd level of the stack the size of the for loop reduces to `2^(n - 1)`\n... and so on. The complexity seems extreamly huge.\nEven when we only consider valid selections on each level, at minimum shouldn\'t the complexity be `16! (16*15*...*2*1)`? Why does it simply not get a TLE?\n```\nclass Solution {\n    private int[] cache, dp;\n\n    private int solve(int mask) {\n        if (dp[mask] == Integer.MAX_VALUE) {\n            dp[mask] = Integer.MAX_VALUE / 2;\n            for (int i = mask; i != 0; i = (i - 1) & mask) {\n                if (cache[i] != Integer.MAX_VALUE) {\n                    dp[mask] = Math.min(dp[mask], cache[i] + solve(mask & ~i));\n                }\n            }\n        }\n        return dp[mask];\n    }\n\n    public int minimumIncompatibility(int[] nums, int k) {\n        int allMask = (1 << nums.length) - 1, size = nums.length / k;\n        Arrays.sort(nums);\n        cache = new int[allMask + 1];\n        dp = new int[allMask + 1];\n        Arrays.fill(cache, Integer.MAX_VALUE);\n        Arrays.fill(dp, Integer.MAX_VALUE);\n        dp[0] = 0;\n        for (int i = 0; i <= allMask; i++) {\n            if (Integer.bitCount(i) != size) continue;\n            int pre = -1, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;\n            for (int j = i, b = 0; j != 0; j >>= 1, b++) {\n                if ((j & 1) == 1) {\n                    if (pre == nums[b]) {\n                        pre = Integer.MIN_VALUE;\n                        break;\n                    }\n                    min = Math.min(min, nums[b]);\n                    max = Math.max(max, nums[b]);\n                    pre = nums[b];\n                }\n            }\n            if (pre != Integer.MIN_VALUE) cache[i] = max - min;\n        }\n        int ans = solve(allMask);\n        return ans >= Integer.MAX_VALUE / 2 ? -1 : ans;\n    }\n}\n```
[]