blob: f61a6b5cf2d71f2e5480d4fcb13dd94e2e0eff2a (
plain)
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
27
28
29
30
31
32
33
34
35
36
|
// 2597. The Number of Beautiful Subsets
#include "leetcode.h"
/*
* given an array 'nums' of positive integers and a positive integer 'k'. a
* subset of 'nums' is beautiful if it does not contain integers with an
* absolute difference equal to 'k'. return the number of non empty beautiful
* subsets of the array 'nums'. a subset of 'nums' is an array that can be
* obtained by deleting some elements from 'nums'. two subsets are different iff
* the chosen indices to delete are different.
*/
int beautifulSubsets(int *nums, int numsSize, int k) {
int n = 1 << numsSize, cnt = 0;
for (int i = 1; i < n; i++) {
int *store = (int *)malloc(numsSize * sizeof(int));
bool flag = true;
for (int j = 0, l = 0; j < numsSize && flag; j++)
if (i & (1 << j)) {
for (int m = 0; m < l && flag; m++)
if (abs(store[m] - nums[j]) == k)
flag = false;
store[l++] = nums[j];
}
if (flag)
cnt++;
free(store);
}
return cnt;
}
int main() {
int n1[] = {2, 4, 6}, n2[] = {1};
printf("%d\n", beautifulSubsets(n1, ARRAY_SIZE(n1), 2)); // expect: 4
printf("%d\n", beautifulSubsets(n2, ARRAY_SIZE(n2), 1)); // expect: 1
}
|