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:

1
2
3

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

Example 2:

1
2
3

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:

1
2
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

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

  1. Sort nums.
  2. Group numbers such that any two numbers in a group differ by a multiple of k.
  3. 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.
  4. Multiply the results for all groups to get the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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 and O(n) for DP, so overall O(n log n)
  • 🧺 Space complexity: O(n) for grouping and DP arrays