Count the Number of K-Free Subsets
MediumUpdated: Aug 2, 2025
Practice on:
Problem
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 ofk-Free subsets of _nums.
A subset of an array is a selection of elements (possibly none) of the array.
Examples
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 <= 501 <= nums[i] <= 10001 <= k <= 1000
Solution
Method 1 – Dynamic Programming on Sorted Groups
Intuition
The key idea is to avoid picking two numbers whose difference is exactly k. By sorting the array and grouping numbers that are k apart, we can use dynamic programming to count valid subsets for each group independently, then multiply the results.
Approach
- Sort nums.
- Group numbers such that any two numbers in a group differ by a multiple of k.
- For each group, use DP:
- Let dp[i] be the number of k-free subsets for the first i elements.
- For each number, either pick it (if previous is not picked) or skip it.
- Multiply the results for all groups to get the answer.
Code
C++
class Solution {
public:
long long countTheNumOfKFreeSubsets(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
long long ans = 1;
int n = nums.size();
vector<vector<int>> groups(k);
for (int x : nums) groups[x % k].push_back(x);
for (auto& g : groups) {
int m = g.size();
if (m == 0) continue;
vector<long long> dp(m + 1);
dp[0] = 1;
dp[1] = 1;
for (int i = 1; i < m; ++i) {
if (g[i] - g[i-1] == k) {
dp[i+1] = dp[i] + dp[i-1];
} else {
dp[i+1] = dp[i] * 2;
}
}
ans *= dp[m];
}
return ans;
}
};
Go
func countTheNumOfKFreeSubsets(nums []int, k int) int64 {
sort.Ints(nums)
ans := int64(1)
groups := make([][]int, k)
for _, x := range nums {
groups[x%k] = append(groups[x%k], x)
}
for _, g := range groups {
m := len(g)
if m == 0 {
continue
}
dp := make([]int64, m+1)
dp[0], dp[1] = 1, 1
for i := 1; i < m; i++ {
if g[i]-g[i-1] == k {
dp[i+1] = dp[i] + dp[i-1]
} else {
dp[i+1] = dp[i] * 2
}
}
ans *= dp[m]
}
return ans
}
Java
class Solution {
public long countTheNumOfKFreeSubsets(int[] nums, int k) {
Arrays.sort(nums);
long ans = 1;
List<Integer>[] groups = new List[k];
for (int i = 0; i < k; i++) groups[i] = new ArrayList<>();
for (int x : nums) groups[x % k].add(x);
for (List<Integer> g : groups) {
int m = g.size();
if (m == 0) continue;
long[] dp = new long[m + 1];
dp[0] = 1; dp[1] = 1;
for (int i = 1; i < m; i++) {
if (g.get(i) - g.get(i-1) == k) {
dp[i+1] = dp[i] + dp[i-1];
} else {
dp[i+1] = dp[i] * 2;
}
}
ans *= dp[m];
}
return ans;
}
}
Kotlin
class Solution {
fun countTheNumOfKFreeSubsets(nums: IntArray, k: Int): Long {
nums.sort()
var ans = 1L
val groups = Array(k) { mutableListOf<Int>() }
for (x in nums) groups[x % k].add(x)
for (g in groups) {
val m = g.size
if (m == 0) continue
val dp = LongArray(m + 1)
dp[0] = 1L; dp[1] = 1L
for (i in 1 until m) {
dp[i+1] = if (g[i] - g[i-1] == k) dp[i] + dp[i-1] else dp[i] * 2
}
ans *= dp[m]
}
return ans
}
}
Python
class Solution:
def countTheNumOfKFreeSubsets(self, nums: list[int], k: int) -> int:
nums.sort()
ans = 1
groups: list[list[int]] = [[] for _ in range(k)]
for x in nums:
groups[x % k].append(x)
for g in groups:
m = len(g)
if m == 0:
continue
dp = [1, 1]
for i in range(1, m):
if g[i] - g[i-1] == k:
dp.append(dp[-1] + dp[-2])
else:
dp.append(dp[-1] * 2)
ans *= dp[-1]
return ans
Rust
impl Solution {
pub fn count_the_num_of_k_free_subsets(nums: Vec<i32>, k: i32) -> i64 {
let mut nums = nums;
nums.sort();
let mut ans = 1i64;
let mut groups = vec![vec![]; k as usize];
for &x in &nums {
groups[(x % k) as usize].push(x);
}
for g in groups.iter() {
let m = g.len();
if m == 0 { continue; }
let mut dp = vec![1i64, 1];
for i in 1..m {
if g[i] - g[i-1] == k {
dp.push(dp[i] + dp[i-1]);
} else {
dp.push(dp[i] * 2);
}
}
ans *= dp[m];
}
ans
}
}
TypeScript
class Solution {
countTheNumOfKFreeSubsets(nums: number[], k: number): number {
nums.sort((a, b) => a - b);
let ans = 1;
const groups: number[][] = Array.from({length: k}, () => []);
for (const x of nums) groups[x % k].push(x);
for (const g of groups) {
const m = g.length;
if (m === 0) continue;
const dp = [1, 1];
for (let i = 1; i < m; ++i) {
if (g[i] - g[i-1] === k) {
dp.push(dp[dp.length-1] + dp[dp.length-2]);
} else {
dp.push(dp[dp.length-1] * 2);
}
}
ans *= dp[dp.length-1];
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n log n)for sorting andO(n)for DP, so overallO(n log n) - 🧺 Space complexity:
O(n)for grouping and DP arrays