# 2638. Count the Number of K-Free Subsets

## Description

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.

A subset of an array is a selection of elements (possibly none) of the array.

Example 1:

Input: nums = [5,4,6], k = 1
Output: 5
Explanation: There are 5 valid subsets: {}, {5}, {4}, {6} and {4, 6}.


Example 2:

Input: nums = [2,3,5,8], k = 5
Output: 12
Explanation: There are 12 valid subsets: {}, {2}, {3}, {5}, {8}, {2, 3}, {2, 3, 5}, {2, 5}, {2, 5, 8}, {2, 8}, {3, 5} and {5, 8}.


Example 3:

Input: nums = [10,5,9,11], k = 20
Output: 16
Explanation: All subsets are valid. Since the total count of subsets is 24 = 16, so the answer is 16.


Constraints:

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 1000
• 1 <= k <= 1000

## Solutions

Solution 1: Grouping + Dynamic Programming

First, sort the array $nums$ in ascending order, and then group the elements in the array according to the remainder modulo $k$, that is, the elements $nums[i] \bmod k$ with the same remainder are in the same group. Then for any two elements in different groups, their absolute difference is not equal to $k$. Therefore, we can obtain the number of subsets in each group, and then multiply the number of subsets in each group to obtain the answer.

For each group $arr$, we can use dynamic programming to obtain the number of subsets. Let $f[i]$ denote the number of subsets of the first $i$ elements, and initially $f[0] = 1$, and $f[1]=2$. When $i \geq 2$, if $arr[i-1]-arr[i-2]=k$, if we choose $arr[i-1]$, then $f[i]=f[i-2]$; If we do not choose $arr[i-1]$, then $f[i]=f[i-1]$. Therefore, when $arr[i-1]-arr[i-2]=k$, we have $f[i]=f[i-1]+f[i-2]$; otherwise $f[i] = f[i - 1] \times 2$. The number of subsets of this group is $f[m]$, where $m$ is the length of the array $arr$.

Finally, we multiply the number of subsets of each group to obtain the answer.

The time complexity is $O(n \times \log n)$ and the space complexity is $O(n)$, where $n$ is the length of the array $nums$.

• 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;
}
}

• class Solution {
public:
long long countTheNumOfKFreeSubsets(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
unordered_map<int, vector<int>> g;
for (int i = 0; i < nums.size(); ++i) {
g[nums[i] % k].push_back(nums[i]);
}
long long ans = 1;
for (auto& [_, arr] : g) {
int m = arr.size();
long long f[m + 1];
f[0] = 1;
f[1] = 2;
for (int i = 2; i <= m; ++i) {
if (arr[i - 1] - arr[i - 2] == k) {
f[i] = f[i - 1] + f[i - 2];
} else {
f[i] = f[i - 1] * 2;
}
}
ans *= f[m];
}
return ans;
}
};

• class Solution:
def countTheNumOfKFreeSubsets(self, nums: List[int], k: int) -> int:
nums.sort()
g = defaultdict(list)
for x in nums:
g[x % k].append(x)
ans = 1
for arr in g.values():
m = len(arr)
f = [0] * (m + 1)
f[0] = 1
f[1] = 2
for i in range(2, m + 1):
if arr[i - 1] - arr[i - 2] == k:
f[i] = f[i - 1] + f[i - 2]
else:
f[i] = f[i - 1] * 2
ans *= f[m]
return ans


• func countTheNumOfKFreeSubsets(nums []int, k int) int64 {
sort.Ints(nums)
g := map[int][]int{}
for _, x := range nums {
g[x%k] = append(g[x%k], x)
}
ans := int64(1)
for _, arr := range g {
m := len(arr)
f := make([]int64, m+1)
f[0] = 1
f[1] = 2
for i := 2; i <= m; i++ {
if arr[i-1]-arr[i-2] == k {
f[i] = f[i-1] + f[i-2]
} else {
f[i] = f[i-1] * 2
}
}
ans *= f[m]
}
return ans
}

• function countTheNumOfKFreeSubsets(nums: number[], k: number): number {
nums.sort((a, b) => a - b);
const g: Map<number, number[]> = new Map();
for (const x of nums) {
const y = x % k;
if (!g.has(y)) {
g.set(y, []);
}
g.get(y)!.push(x);
}
let ans: number = 1;
for (const [_, arr] of g) {
const m = arr.length;
const f: number[] = new Array(m + 1).fill(1);
f[1] = 2;
for (let i = 2; i <= m; ++i) {
if (arr[i - 1] - arr[i - 2] === k) {
f[i] = f[i - 1] + f[i - 2];
} else {
f[i] = f[i - 1] * 2;
}
}
ans *= f[m];
}
return ans;
}