Count the number of k free subsets

Array Math Dynamic Programming Sorting Combinatorics

47.2% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_the_num_of_k_free_subsets(nums: Vec<i32>, k: i32) -> i64 {
    use std::collections::HashMap;
    let mut groups: HashMap<i32, Vec<i32>> = HashMap::new();
    for &x in &nums {
      groups.entry(x % k).or_default().push(x);
    }
    let mut result: i64 = 1;
    for (_, mut group) in groups {
      group.sort();
      let mut dp = [1i64, 1i64];
      for i in 1..group.len() {
        let new_dp = if group[i] - group[i - 1] == k {
          [dp[0] + dp[1], dp[0]]
        } else {
          [dp[0] + dp[1], dp[0] + dp[1]]
        };
        dp = new_dp;
      }
      result *= dp[0] + dp[1];
    }
    result
  }
}