# Count the number of K Free Subsets

You are given an integer array nums, which contains **distinct** elements and an integer k.

A subset is called a **k-Free** subset if it contains **no** two elements with an absolute difference equal to k. Notice that the empty set is a **k-Free** subset.

Return *the number of ***k-Free*** subsets of *nums.

```
//Solution 1
class Solution {
public long countTheNumOfKFreeSubsets(int[] nums, int k) {
Arrays.sort(nums);
Map<Integer, List<Integer>> g = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
g.computeIfAbsent(nums[i] % k, x -> new ArrayList<>()).add(nums[i]);
}
long ans = 1;
for (var arr : g.values()) {
int m = arr.size();
long[] f = new long[m + 1];
f[0] = 1;
f[1] = 2;
for (int i = 2; i <= m; ++i) {
if (arr.get(i - 1) - arr.get(i - 2) == k) {
f[i] = f[i - 1] + f[i - 2];
} else {
f[i] = f[i - 1] * 2;
}
}
ans *= f[m];
}
return ans;
}
}
```

```
//Solution 2
class Solution {
public long countTheNumOfKFreeSubsets(int[] nums, int k) {
Map<Integer, Set<Integer>> modToSubset = new HashMap<>();
for (final int num : nums) {
modToSubset.putIfAbsent(num % k, new TreeSet<>());
modToSubset.get(num % k).add(num);
}
int prevNum = -k;
long skip = 0;
long pick = 0;
for (Set<Integer> subset : modToSubset.values())
for (final int num : subset) {
final long cacheSkip = skip;
skip += pick;
pick = 1 + cacheSkip + (num - prevNum == k ? 0 : pick);
prevNum = num;
}
return 1 + skip + pick;
}
}
```

```
class Solution:
def countTheNumOfKFreeSubsets(self, nums: list[int], k: int) -> int:
modToSubset = collections.defaultdict(set)
for num in nums:
modToSubset[num % k].add(num)
prevNum = -k
skip = 0
pick = 0
for subset in modToSubset.values():
for num in sorted(subset):
skip, pick = (skip + pick,
1 + skip + (0 if num - prevNum == k else pick))
prevNum = num
return 1 + skip + pick
```

The solution to the k-Free subset problem revolves around breaking the array into groups based on their remainders when divided by k. This works because elements in different groups cannot have an absolute difference equal to k, allowing subsets to be formed freely within each group. By sorting the array and assigning each element to a group based on its remainder, we avoid conflicts between numbers that could violate the k-Free condition.

Once the array is grouped, the problem reduces to calculating the number of valid subsets within each group. The key is to decide for each element whether to include it in the subset based on whether its difference from the previous element is equal to k. By keeping track of two possibilities—whether to skip or pick an element—we can efficiently calculate the total number of valid subsets for the entire array by multiplying the results from each group.

## Related Problems

Given a string s, partition s such that every substring of the partition is a palindrome.

Return *the ***minimum*** cuts needed for a palindrome partitioning of* s.

Given an integer array nums, return *the length of the longest ***strictly increasing subsequence**.

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return *the maximum coins you can collect by bursting the balloons wisely*.