The Number of Beautiful Subsets

1. Initialize a counter beautifulSubsetsCount to 0.
2. Determine the size of the input array, n.
3. Iterate through all possible non-empty subsets using a bitmask. Loop an integer i from 1 to (1 << n) - 1.
4. For each i, construct the corresponding subset:
   • Create an empty list subset.
   • Iterate from j = 0 to n - 1. If the j-th bit of i is set, add nums[j] to subset.
5. Check if the generated subset is beautiful:
   • Assume the subset is beautiful (isBeautiful = true).
   • Iterate through all pairs of elements (x, y) in the subset.
   • If abs(x - y) == k, set isBeautiful = false and break the inner loops.
6. If isBeautiful is still true after checking all pairs, increment beautifulSubsetsCount.
7. After iterating through all bitmasks, return beautifulSubsetsCount.

The most straightforward way to solve this problem is to generate all 2^n - 1 non-empty subsets of nums. A common technique for this is using bit manipulation, where each integer from 1 to 2^n - 1 represents a unique subset. The j-th bit of the integer corresponds to the j-th element of the nums array. If the bit is 1, the element is included in the subset.

Once a subset is formed, we must validate if it's beautiful. This is done by comparing every pair of elements in the subset. If we find any pair (a, b) such that abs(a - b) == k, the subset is not beautiful, and we can stop checking it and move to the next subset. If all pairs are checked and the condition is never met, we increment our count of beautiful subsets.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int beautifulSubsets(int[] nums, int k) {6        int n = nums.length;7        int beautifulSubsetsCount = 0;8 9        for (int i = 1; i < (1 << n); i++) {10            List<Integer> subset = new ArrayList<>();11            for (int j = 0; j < n; j++) {12                if ((i >> j & 1) == 1) {13                    subset.add(nums[j]);14                }15            }16 17            if (isBeautiful(subset, k)) {18                beautifulSubsetsCount++;19            }20        }21 22        return beautifulSubsetsCount;23    }24 25    private boolean isBeautiful(List<Integer> subset, int k) {26        int size = subset.size();27        for (int i = 0; i < size; i++) {28            for (int j = i + 1; j < size; j++) {29                if (Math.abs(subset.get(i) - subset.get(j)) == k) {30                    return false;31                }32            }33        }34        return true;35    }36}

1. Define a recursive helper function, e.g., countBeautiful(index, freqMap).
2. The main function initializes the process by calling countBeautiful(0, new HashMap<>()) and subtracts 1 from the result to exclude the empty set.
3. The recursive function countBeautiful(index, freqMap):
   • Base Case: If index == nums.length, it means we've considered all elements, forming one valid combination (which could be an empty subset for the subproblem). Return 1.
   • Recursive Step: a. Skip nums[index]: Calculate the number of beautiful subsets without including the current element. This is a recursive call: countBeautiful(index + 1, freqMap). b. Take nums[index]: Check if this is a valid move. The element nums[index] can be taken only if nums[index] - k and nums[index] + k are not present in the current subset (i.e., not in freqMap).
     • If it's valid:
       • Add nums[index] to freqMap.
       • Recursively call countBeautiful(index + 1, freqMap) to get the count for the rest of the array.
       • Backtrack: remove nums[index] from freqMap to explore other possibilities. c. Sum the counts from the 'skip' and 'take' (if valid) paths.
4. Return the total count.

This method uses a recursive depth-first search (DFS) to explore all possibilities. A helper function, say solve(index), is defined to compute the number of beautiful subsets that can be formed using elements from nums[index] to nums[n-1].

To keep track of the elements in the current subset being built, we use a frequency map or a set. When considering nums[index], we first check if adding it would violate the condition. Specifically, we check if nums[index] - k or nums[index] + k is already in our frequency map. If neither is present, we can include nums[index].

The total count is the sum of possibilities from two branches:

1. Skipping nums[index] and moving to solve(index + 1).
2. Including nums[index] (if valid), updating the frequency map, and then moving to solve(index + 1).

After the recursive call for the 'include' case, we must backtrack by removing nums[index] from the frequency map. The final result is the total count returned by the initial call solve(0) minus one (for the empty set).

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    private int count = 0;6    private int k;7    private int[] nums;8 9    public int beautifulSubsets(int[] nums, int k) {10        this.k = k;11        this.nums = nums;12        // Using a map to store frequencies of elements in the current subset.13        Map<Integer, Integer> freqMap = new HashMap<>();14        solve(0, freqMap);15        return count - 1; // Subtract 1 for the empty subset16    }17 18    private void solve(int index, Map<Integer, Integer> freqMap) {19        if (index == nums.length) {20            count++;21            return;22        }23 24        // Option 1: Don't include nums[index]25        solve(index + 1, freqMap);26 27        // Option 2: Include nums[index]28        int currentElement = nums[index];29        if (!freqMap.containsKey(currentElement - k) && !freqMap.containsKey(currentElement + k)) {30            freqMap.put(currentElement, freqMap.getOrDefault(currentElement, 0) + 1);31            solve(index + 1, freqMap);32            // Backtrack33            freqMap.put(currentElement, freqMap.get(currentElement) - 1);34            if (freqMap.get(currentElement) == 0) {35                freqMap.remove(currentElement);36            }37        }38    }39}

1. Count the frequency of each number in nums and store it in a map.
2. Group the unique numbers from nums based on their remainder when divided by k. Store these groups in a map, e.g., Map<Integer, List<Integer>>.
3. Initialize a variable totalSubsets to 1. This will store the product of counts from all groups.
4. For each group of numbers: a. Sort the numbers in the group. b. Apply dynamic programming to find the number of beautiful subsets within this group (including the empty set). c. Let g = [x_0, x_1, ..., x_m] be the sorted unique numbers in the group. d. Initialize skip = 1 (representing not taking the previous element, starting with the empty set) and take = 0 (representing taking the previous element). e. Iterate through x_i in g: i. Calculate subsetsWithXi = 2^freq(x_i) - 1. ii. newSkip = skip + take (total ways for prefix i-1). iii. If x_i - x_{i-1} == k, we cannot take x_{i-1}. So, newTake = skip * subsetsWithXi. iv. Otherwise, newTake = (skip + take) * subsetsWithXi. v. Update skip = newSkip and take = newTake. f. The total for the group is skip + take. g. Multiply totalSubsets by this group total.
5. The final result is totalSubsets - 1.

First, we process the input nums to get the frequency of each number. Then, we partition the unique numbers into groups based on their value modulo k. For example, if k=3, numbers 1, 4, 7 would be in one group, and 2, 5, 8 in another.

The choices within one group are independent of choices in another. For instance, picking 4 (rem 1) doesn't restrict picking 5 (rem 2), as abs(5-4) != 3. So, we can find the number of beautiful subsets for each group (including the empty set), and multiply these counts together.

To solve the subproblem for a single group, we use dynamic programming. Let's say a sorted group of unique numbers is g' = [x_1, x_2, ..., x_m]. We iterate through g' and maintain two counts: skip, the number of beautiful subsets of the prefix that don't include the current element, and take, the number that do. When considering x_i, the number of ways to form non-empty subsets with its duplicates is 2^freq(x_i) - 1. If x_i - x_{i-1} == k, we can only extend subsets that didn't include x_{i-1}. Otherwise, we can extend any valid subset from the prefix.

Finally, we multiply the results from all groups and subtract one to exclude the case where we pick the empty set from every group.

1import java.util.*;2 3class Solution {4    public int beautifulSubsets(int[] nums, int k) {5        Map<Integer, Integer> freqMap = new HashMap<>();6        for (int num : nums) {7            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);8        }9 10        Map<Integer, List<Integer>> groups = new HashMap<>();11        for (int num : freqMap.keySet()) {12            int remainder = num % k;13            groups.computeIfAbsent(remainder, key -> new ArrayList<>()).add(num);14        }15 16        long totalWays = 1;17        for (List<Integer> group : groups.values()) {18            Collections.sort(group);19            totalWays *= countBeautifulInGroup(group, freqMap, k);20        }21 22        return (int) (totalWays - 1);23    }24 25    private long countBeautifulInGroup(List<Integer> group, Map<Integer, Integer> freqMap, int k) {26        long skip = 1; // Ways for prefix ending at i-1, not taking element i-127        long take = 0; // Ways for prefix ending at i-1, taking element i-128 29        for (int i = 0; i < group.size(); i++) {30            long subsetsWithCurrent = (1L << freqMap.get(group.get(i))) - 1;31            long newSkip = skip + take;32            long newTake;33 34            if (i > 0 && group.get(i) - group.get(i - 1) == k) {35                newTake = skip * subsetsWithCurrent;36            } else {37                newTake = (skip + take) * subsetsWithCurrent;38            }39            skip = newSkip;40            take = newTake;41        }42        return skip + take;43    }44}