playground/leetcode/2597-the-number-of-beautiful-subsets/2597-the-number-of-beautiful-subsets.cpp at main · MuhtasimTanmoy/playground · GitHub

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// class Solution {
// public:
//     int beautifulSubsets(vector<int>& nums, int k) {
//         unordered_multiset<int> bag;
//         int res = 0;
//         for (auto l = 0, r = 0; r < nums.size(); r++) {
//             auto on_l = nums[r] + k, on_r = nums[r] - k;
//             while (bag.count(on_l) || bag.count(on_r))
//                    bag.erase(bag.find(nums[l++]));
//             res += r - l + 1;
//             bag.insert(nums[r]);
//         }
//         return res;
//     }
// };


// class Solution {
// public:
//     int beautifulSubsets(vector<int>& nums, int k) {
//         unordered_map<int, int> counter;
//         int res = 0;
//         for (auto i = 0; i < nums.size(); i++) {
//             auto find_l = nums[i] - k, find_r = nums[i] + k;

//             int deduct = 0;
//             if (counter.count(find_l)) deduct += counter[find_l];
//             if (counter.count(find_r)) deduct += counter[find_r];

//             res += i + 1 - deduct;
//             cout<<res<<endl;
//             counter[nums[i]]++;
//         }
//         return res;
//     }
// };


class Solution {
public:
    int beautifulSubsets(vector<int>& N, int k) {
        unordered_map<int, int> counter;
        int n = N.size();
        function<int(int)> go = [&](auto i) {
            if (i == n) return 1;
            int res = go(i + 1);
            if (!counter[N[i] + k] && !counter[N[i] - k])
                counter[N[i]]++,
                res += go(i + 1),
                counter[N[i]]--;
            return res;
        };
        return go(0) - 1;
    }
};