Count the Number of K-Free Subsets - Practice Coding Problems

Count the Number of K-Free Subsets - 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 of k-Free subsets of nums.

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

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,7,9], k = 3

› Output: 6

💡 Note: K-free subsets are: {}, {4}, {7}, {9}, {4,9}, {7,9}. Cannot include {4,7} or {4,7,9} because |4-7|=3=k.

Example 2 — No Conflicts

$ Input: nums = [2,5,8], k = 4

› Output: 8

💡 Note: No two elements differ by 4, so all 2³=8 subsets are k-free: {}, {2}, {5}, {8}, {2,5}, {2,8}, {5,8}, {2,5,8}.

Example 3 — Multiple Conflicts

$ Input: nums = [1,4,7,10], k = 3

› Output: 8

💡 Note: Conflicts: 1-4=3, 4-7=3, 7-10=3. Elements form a chain where adjacent elements can't coexist.

Constraints

1 ≤ nums.length ≤ 20
1 ≤ nums[i] ≤ 1000
0 ≤ k ≤ 1000
nums contains distinct elements

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums=[4,7,9] and k=3

Find Conflicts

Identify pairs with absolute difference equal to k

Count Valid

Count subsets avoiding conflicting pairs

Key Takeaway

🎯 Key Insight: Group elements by remainder mod k to isolate conflicts, then apply DP within each group

Asked in

G Google 35 a Amazon 28 M Microsoft 22

The key insight is to recognize this as a variant of the House Robber problem after sorting. Elements that differ by exactly k cannot both be included. Best approach uses Dynamic Programming with grouping by remainder mod k. Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming - Optimized	O(n²)	O(n)	Use 1D DP after sorting to efficiently count k-free subsets
Sort and Group by Remainder	O(n log n + n × 2ᵍ)	O(n)	Sort numbers and group by remainder when divided by k, then use dynamic programming
Brute Force - Generate All Subsets	O(n² × 2ⁿ)	O(1)	Generate all 2^n possible subsets and check each one for k-free property

Dynamic Programming - Optimized — Algorithm Steps

Sort the array to identify potential conflicts easily
Use DP: dp[i] represents number of k-free subsets using elements 0 to i
For each element, check if it conflicts with previous elements

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Sort to process elements in order

DP Transition

For each element: exclude it OR include if no conflicts

Final Count

DP[n] contains total k-free subsets

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* nums, int numsSize, int k) {
    qsort(nums, numsSize, sizeof(int), compare);
    
    // dp[i] = number of k-free subsets using elements from index 0 to i
    int dp[21];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1; // empty subset
    
    for (int i = 0; i < numsSize; i++) {
        // Option 1: don't include nums[i]
        dp[i + 1] = dp[i];
        
        // Option 2: include nums[i]
        int j = i - 1;
        while (j >= 0 && abs(nums[i] - nums[j]) == k) {
            j--;
        }
        
        dp[i + 1] += dp[j + 1];
    }
    
    return dp[numsSize];
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[20];
    int numsSize = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Sorting takes O(n log n), DP with conflict checking takes O(n²)

⚠ Quadratic Growth

Space Complexity

O(n)

DP array and sorted array storage

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming - Optimized — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler