Count the Number of K-Free Subsets - Video Solutions

Problem Overview: Given an integer array nums and an integer k, count how many subsets contain no pair of elements whose difference equals k. Any subset is valid as long as for every pair (a, b), |a - b| != k. The challenge is avoiding combinations that contain values spaced exactly k apart while still counting all valid subsets efficiently.

Approach 1: Brute Force Subset Enumeration (O(2^n * n), O(n))

Generate every possible subset using recursion or bitmasks, then verify whether it is k-free. For each subset, iterate through all pairs and check if the absolute difference equals k. This guarantees correctness but quickly becomes infeasible because the number of subsets grows exponentially. This approach mainly helps understand the constraint and verify small test cases before optimizing.

Approach 2: Sort + Conflict Checking with Set (O(n log n), O(n))

Sort the array so numbers with difference k appear near each other. While iterating, track chosen numbers in a hash set. If num - k already exists in the set, selecting num would violate the constraint. Although sorting simplifies conflict detection, counting all valid subsets still requires dynamic decisions for each element. This observation leads directly to a structured dynamic programming formulation.

Approach 3: Grouping by Remainder + Dynamic Programming (O(n log n), O(n))

The key insight: numbers that differ by exactly k must share the same remainder when divided by k. Group elements by num % k. Inside each group, sort the values and process them like a non-adjacent selection problem. If two values differ by k, selecting one blocks the other. This forms a structure similar to the House Robber problem.

For each sorted group, compress equal values and count their frequency. When processing value x, compute the number of ways to either include or skip it. If the previous value in the group is exactly x - k, the DP transition prevents selecting both simultaneously. Otherwise, the states combine freely. Multiply the number of valid subsets from all groups to obtain the final result.

This technique reduces the global constraint into several independent chains, which dramatically simplifies counting. Sorting handles ordering, while dynamic programming tracks valid combinations within each chain. The preprocessing step relies on arrays and optional sorting to structure the groups.

Recommended for interviews: The grouping + dynamic programming solution is the expected approach. Interviewers want to see the observation that conflicts only occur within the same num % k group and that each group forms a DP chain similar to House Robber. Mentioning the brute force approach first shows you understand the constraint space, but implementing the grouped DP demonstrates strong problem decomposition and combinatorial counting skills.