2638. Count the Number of K-Free Subsets π
Description
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.
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 <= 50
1 <= nums[i] <= 1000
1 <= k <= 1000
Solutions
Solution 1: Grouping + Dynamic Programming
First, sort the array $nums$ in ascending order, and then group the elements in the array according to the remainder modulo $k$, that is, the elements $nums[i] \bmod k$ with the same remainder are in the same group. Then for any two elements in different groups, their absolute difference is not equal to $k$. Therefore, we can obtain the number of subsets in each group, and then multiply the number of subsets in each group to obtain the answer.
For each group $arr$, we can use dynamic programming to obtain the number of subsets. Let $f[i]$ denote the number of subsets of the first $i$ elements, and initially $f[0] = 1$, and $f[1]=2$. When $i \geq 2$, if $arr[i-1]-arr[i-2]=k$, if we choose $arr[i-1]$, then $f[i]=f[i-2]$; If we do not choose $arr[i-1]$, then $f[i]=f[i-1]$. Therefore, when $arr[i-1]-arr[i-2]=k$, we have $f[i]=f[i-1]+f[i-2]$; otherwise $f[i] = f[i - 1] \times 2$. The number of subsets of this group is $f[m]$, where $m$ is the length of the array $arr$.
Finally, we multiply the number of subsets of each group to obtain the answer.
The time complexity is $O(n \times \log n)$ and the space complexity is $O(n)$, where $n$ is the length of the array $nums$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
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 |
|
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
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 |
|