# The Number of Beautiful Subsets
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/the-number-of-beautiful-subsets)
Canonical: https://scaleengineer.com/dsa/problems/the-number-of-beautiful-subsets
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## Problem
You are given an array `nums` of positive integers and a **positive** integer `k`.

A subset of `nums` is **beautiful** if it does not contain two integers with an absolute difference equal to `k`.

Return _the number of **non-empty beautiful** subsets of the array_ `nums`.

A **subset** of `nums` is an array that can be obtained by deleting some (possibly none) elements from `nums`. Two subsets are different if and only if the chosen indices to delete are different.

**Example 1:**

**Input:** nums = [2,4,6], k = 2
**Output:** 4
**Explanation:** The beautiful subsets of the array nums are: [2], [4], [6], [2, 6].
It can be proved that there are only 4 beautiful subsets in the array [2,4,6].

**Example 2:**

**Input:** nums = [1], k = 1
**Output:** 1
**Explanation:** The beautiful subset of the array nums is [1].
It can be proved that there is only 1 beautiful subset in the array [1].

**Constraints:**

* `1 <= nums.length <= 18`
* `1 <= nums[i], k <= 1000`

# Approaches
## Brute-force Subset Generation
This approach involves generating every possible non-empty subset of the given array `nums`. For each subset, a check is performed to see if it meets the 'beautiful' criteria, which means no two elements within the subset have an absolute difference equal to `k`. A counter is maintained for all subsets that satisfy this condition.
**Time:** O(2^N * N^2), where N is the length of `nums`. There are `2^N` subsets. For each subset of size `s`, we take O(N) to build it and O(s^2) (at most O(N^2)) to check if it's beautiful. · **Space:** O(N), where N is the length of `nums`. This space is used to store the current subset being checked.
**Pros:** Conceptually simple and easy to implement.; Works correctly for small input sizes.
**Cons:** Highly inefficient due to its time complexity.; Will likely result in a 'Time Limit Exceeded' error for larger constraints (e.g., N > 16).
### Explanation
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.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int beautifulSubsets(int[] nums, int k) {
        int n = nums.length;
        int beautifulSubsetsCount = 0;

        for (int i = 1; i < (1 << n); i++) {
            List<Integer> subset = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if ((i >> j & 1) == 1) {
                    subset.add(nums[j]);
                }
            }

            if (isBeautiful(subset, k)) {
                beautifulSubsetsCount++;
            }
        }

        return beautifulSubsetsCount;
    }

    private boolean isBeautiful(List<Integer> subset, int k) {
        int size = subset.size();
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                if (Math.abs(subset.get(i) - subset.get(j)) == k) {
                    return false;
                }
            }
        }
        return true;
    }
}
```
### Algorithm
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`.

## Backtracking
A more optimized approach uses backtracking to build the subsets. We traverse through the `nums` array, and for each element, we decide whether to include it in our subset or not. We only add an element if it doesn't violate the 'beautiful' condition with the elements already chosen. This way, we avoid generating invalid subsets from the start, effectively pruning the search space.
**Time:** O(2^N). The recursion tree has `2^N` states, and in each state, we perform constant time operations (map lookups). · **Space:** O(N + M), where N is the recursion depth and M is the number of unique values in `nums` for the HashMap. If an array is used as a frequency map, it would be O(N + max_val).
**Pros:** Significantly faster than the brute-force approach.; Efficient enough to pass for constraints like N <= 20.
**Cons:** The time complexity is still exponential, making it unsuitable for N significantly larger than 20.; The space complexity depends on the range of values in `nums` if an array is used as a frequency map, though a HashMap mitigates this.
### Explanation
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).

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    private int count = 0;
    private int k;
    private int[] nums;

    public int beautifulSubsets(int[] nums, int k) {
        this.k = k;
        this.nums = nums;
        // Using a map to store frequencies of elements in the current subset.
        Map<Integer, Integer> freqMap = new HashMap<>();
        solve(0, freqMap);
        return count - 1; // Subtract 1 for the empty subset
    }

    private void solve(int index, Map<Integer, Integer> freqMap) {
        if (index == nums.length) {
            count++;
            return;
        }

        // Option 1: Don't include nums[index]
        solve(index + 1, freqMap);

        // Option 2: Include nums[index]
        int currentElement = nums[index];
        if (!freqMap.containsKey(currentElement - k) && !freqMap.containsKey(currentElement + k)) {
            freqMap.put(currentElement, freqMap.getOrDefault(currentElement, 0) + 1);
            solve(index + 1, freqMap);
            // Backtrack
            freqMap.put(currentElement, freqMap.get(currentElement) - 1);
            if (freqMap.get(currentElement) == 0) {
                freqMap.remove(currentElement);
            }
        }
    }
}
```
### Algorithm
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.

## Dynamic Programming with Grouping
This highly efficient approach is based on a key observation: the beautiful subset condition `abs(x - y) == k` only creates dependencies between numbers `x` and `y` if they have the same remainder modulo `k`. This allows us to partition the numbers into groups based on their remainder `num % k`. The problem can then be solved for each group independently, and the final results can be combined.

The number of beautiful subsets for the entire array is the product of the number of beautiful subsets from each group. For each group, we use dynamic programming to count its beautiful subsets. This subproblem is equivalent to finding the number of ways to choose elements from a sequence such that no two chosen elements are adjacent if their difference is `k`.
**Time:** O(N log N), where N is the length of `nums`. The dominant operations are counting frequencies (O(N)), grouping (O(N)), and then for each group, sorting and iterating. The sum of `S_g log S_g` over all groups is at most O(N log N). · **Space:** O(N), where N is the length of `nums`. This space is for the frequency map and the groups map.
**Pros:** Extremely efficient with a polynomial time complexity.; Scales well even if N were larger.
**Cons:** More complex to conceptualize and implement compared to the other approaches.
### Explanation
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.

```java
import java.util.*;

class Solution {
    public int beautifulSubsets(int[] nums, int k) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int num : freqMap.keySet()) {
            int remainder = num % k;
            groups.computeIfAbsent(remainder, key -> new ArrayList<>()).add(num);
        }

        long totalWays = 1;
        for (List<Integer> group : groups.values()) {
            Collections.sort(group);
            totalWays *= countBeautifulInGroup(group, freqMap, k);
        }

        return (int) (totalWays - 1);
    }

    private long countBeautifulInGroup(List<Integer> group, Map<Integer, Integer> freqMap, int k) {
        long skip = 1; // Ways for prefix ending at i-1, not taking element i-1
        long take = 0; // Ways for prefix ending at i-1, taking element i-1

        for (int i = 0; i < group.size(); i++) {
            long subsetsWithCurrent = (1L << freqMap.get(group.get(i))) - 1;
            long newSkip = skip + take;
            long newTake;

            if (i > 0 && group.get(i) - group.get(i - 1) == k) {
                newTake = skip * subsetsWithCurrent;
            } else {
                newTake = (skip + take) * subsetsWithCurrent;
            }
            skip = newSkip;
            take = newTake;
        }
        return skip + take;
    }
}
```
### Algorithm
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`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int BeautifulSubsets(int[] nums, int k) {
        int ans = -1;
        int[] cnt = new int[1010];
        int n = nums.Length;
        void Dfs(int i) {
            if (i >= n) {
                ans++;
                return;
            }
            Dfs(i + 1);
            bool ok1 = nums[i] + k >= 1010 || cnt[nums[i] + k] == 0;
            bool ok2 = nums[i] - k < 0 || cnt[nums[i] - k] == 0;
            if (ok1 && ok2) {
                cnt[nums[i]]++;
                Dfs(i + 1);
                cnt[nums[i]]--;
            }
        }
        Dfs(0);
        return ans;
    }
}
```

### Java

```java
class Solution {
private
  int[] nums;
private
  int[] cnt = new int[1010];
private
  int ans = -1;
private
  int k;
public
  int beautifulSubsets(int[] nums, int k) {
    this.k = k;
    this.nums = nums;
    dfs(0);
    return ans;
  }
private
  void dfs(int i) {
    if (i >= nums.length) {
      ++ans;
      return;
    }
    dfs(i + 1);
    boolean ok1 = nums[i] + k >= cnt.length || cnt[nums[i] + k] == 0;
    boolean ok2 = nums[i] - k < 0 || cnt[nums[i] - k] == 0;
    if (ok1 && ok2) {
      ++cnt[nums[i]];
      dfs(i + 1);
      --cnt[nums[i]];
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int beautifulSubsets(vector<int> &nums, int k) {
    int ans = -1;
    int cnt[1010]{};
    int n = nums.size();
    function<void(int)> dfs = [&](int i) {
      if (i >= n) {
        ++ans;
        return;
      }
      dfs(i + 1);
      bool ok1 = nums[i] + k >= 1010 || cnt[nums[i] + k] == 0;
      bool ok2 = nums[i] - k < 0 || cnt[nums[i] - k] == 0;
      if (ok1 && ok2) {
        ++cnt[nums[i]];
        dfs(i + 1);
        --cnt[nums[i]];
      }
    };
    dfs(0);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int: def dfs(i: int) -> None: nonlocal ans if i >= len(nums): ans += 1 return dfs(i + 1) if cnt[nums[i] + k] == 0 and cnt[nums[i] - k] == 0: cnt[nums[i]] += 1 dfs(i + 1) cnt[nums[i]] -= 1 ans = - 1 cnt = Counter() dfs(0) return ans

```