Java || 2ms 100% O(n log n) || Bitmasks, Skip fully beautiful values
This code takes advantage of the values 0 through 2^n-1 being a binary bitmask representation of all possible subsets of nums values, where n is the number of v
This code takes advantage of the values 0 through 2^n-1 being a binary bitmask representation of all possible subsets of nums values, where n is the number of values in the nums array.  In the binary bitmasks, a 1 bit in the i\'th bit position means that nums[i] is included in the subset.  A 0 bit in the i\'th bit position means that nums[i] is excluded from the subset.  The goal of this problem is to determine which binary bitmask representations are beautiful and which are not beautiful.  Also, for the bitmask value of all zeroes, the empty subset, this is not counted as a beautiful subset of nums, because the empty subset is explicitly excluded in the description for this leetcode problem.\n\n**Algorithm:**\n\n1. Build array of bitmasks for which nums[i] are incompatible with nums[j] where j<i.  The bit positions in the bitmasks are the index into the nums array.  In the bitmask for nums[i], if the j\'th bit in the bitmask (bit at 1<<j) is a 1, then nums[i] and nums[j] are not compatible for making a beautiful subset.  The bitmasks are stored in the `bads[]` array.\n2. Search through the bitmasks in the `bads[]` array to find zero values.  If the bitmask at bads[i] is all zeroes, then the nums[i] is "fully-beautiful" and nums[i] is compatible with all other nums[] values for making beautiful subsets.  Fully-beautiful nums[i] values will be skipped in later recursively trying combinations of nums values.  If there are x fully-beautiful nums values (x values fully compatible with all other nums values), then the fully-beautiful values, considered just by themselves, will form 2 to the x\'th power beautiful subsets (including the empty subset).\n3. Recursively try all combinations of non-fully-beautiful nums values, using the bitmasks to quickly determine a proposed subset that is not beautiful.  Count the number of beautiful subsets (including the empty set) of all non-fully-beautiful nums values.  During recursion, skip over any nums value that is fully-beautiful (has a bitmask of all zeroes).\n4. Return the result of the previous recursion\'s count of number of beautiful subsets of non-fully-beautiful nums values, combined with all possible subsets of fully-beautiful nums values (2 to the power of the count of fully beautiful nums values), minus 1 since the empty subset is not allowed as an beautiful subset in this leetcode problem.\n\nThe code below has a runtime of 2ms in May 2024.\n\n**----- Clean Java Code -----**\n(Commented code further below)\n```\nclass Solution {\n    int beautifulCount = 0;\n    \n    public int beautifulSubsets(int[] nums, int k) {\n        int n = nums.length;\n        int[] bads = new int[n];\n        int used = 1 << n;\n        for (int i = 0; i < n; i++) {\n            int badBits = 0;\n            int numsI = nums[i];\n            for (int j = 0; j < i; j++) {\n                if (Math.abs(numsI - nums[j]) == k) {\n                    badBits |= (1 << j);\n                    bads[j] |= used;\n                }\n            }\n            bads[i] = badBits;\n        }\n        \n        int fullBeautiful = 1;\n        for (int i = n - 1; i >= 0; i--)\n            if (bads[i] == 0)\n                fullBeautiful <<= 1;\n        \n        tryCombo(0, 0, bads);\n        return beautifulCount * fullBeautiful - 1;  // Subtract 1 for empty set.\n    }\n    \n    \n    private void tryCombo(int idx, int bits, int[] bads) {\n        while (idx < bads.length && bads[idx] == 0)  idx++;\n        \n        if (idx >= bads.length) {\n            beautifulCount++;\n            return;\n        }\n        \n        tryCombo(idx + 1, bits, bads);\n        bits |= (1 << idx);\n        if ((bads[idx] & bits) == 0) \n            tryCombo(idx + 1, bits, bads);\n    }\n}\n```\n\n**----- Commented Java Code -----**\n```\nclass Solution {\n    int beautifulCount = 0;\n    \n    public int beautifulSubsets(int[] nums, int k) {\n        // For each value in nums[] array, create a bitmask in bads[] array, \n        // showing which other nums[] values it is not beautiful with.  i.e. \n        // For each nums[i], create a bitmask in bads[i], where the bit (1<<j) \n        // is set to one if abs(nums[i]-nums[j])==k.\n        int n = nums.length;\n        int[] bads = new int[n];\n        int used = 1 << n;\n        for (int i = 0; i < n; i++) {\n            int badBits = 0;\n            int numsI = nums[i];\n            for (int j = 0; j < i; j++) {\n                if (Math.abs(numsI - nums[j]) == k) {\n                    badBits |= (1 << j);\n                    bads[j] |= used;\n                }\n            }\n            bads[i] = badBits;\n        }\n        \n        // Find nums[i] which are fully beautiful with ALL other nums[] values.  \n        // i.e. Find bads[i] values that are 0, indicating there are no \n        // non-beautiful values for nums[i] in all the other nums[] values.  \n        // All fully beautiful values can be removed from more detailed \n        // calculations, and be accounted for at the end.\n        int fullBeautiful = 1;\n        for (int i = n - 1; i >= 0; i--)\n            if (bads[i] == 0)\n                fullBeautiful <<= 1;\n        \n        // Do recursive trying of possible sets that don\'t include fully \n        // beautiful numbers (nums[] values fully compatible with ALL other \n        // nums[] values), getting a count of the number of possible sets.  \n        // Apply the possible sets of fully beautiful numbers when done with \n        // recursion.\n        tryCombo(0, 0, bads);\n        return beautifulCount * fullBeautiful - 1;  // Subtract 1 for empty set.\n    }\n    \n    \n    // Recursive method to try combinations of leaving a nums[i] value out of \n    // a set, and also including nums[i] in a set.  Start at nums[0] and recurse \n    // to go to the next nums[] value, until the end of nums[].  If trying to \n    // include a nums[] value in the set, if that nums[] value is in conflict \n    // with previously included members of the set, then stop working with this \n    // subset of nums, because it will always be non-beautiful.  Skip any nums[] \n    // values that are fully beautiful (conpatible with all other nums[] values) \n    // because these will be included in the count when all recursion is complete.\n    private void tryCombo(int idx, int bits, int[] bads) {\n        // Skip fully beautiful nums[] values.\n        while (idx < bads.length && bads[idx] == 0)  idx++;\n        \n        // If reached the end of nums[], then count another good set.\n        if (idx >= bads.length) {\n            beautifulCount++;\n            return;\n        }\n        \n        // Try recursing without including the current nums[idx] value in the set, \n        // then if nums[idx] is not in conflict with previous members of the set, \n        // then recurse with including the current nums[idx] value in the set.\n        tryCombo(idx + 1, bits, bads);\n        bits |= (1 << idx);\n        if ((bads[idx] & bits) == 0) \n            tryCombo(idx + 1, bits, bads);\n    }\n}\n```
['Java']