[C++] O(nlogn) Grouping beats 100%
Approach\nFrom the example case $[2,4,6]$ and $k = 2$, we can see that numbers can be grouped with regard to $k$. Define a group to be unique numbers which are 
# Approach\nFrom the example case $[2,4,6]$ and $k = 2$, we can see that numbers can be grouped with regard to $k$. Define a group to be unique numbers which are exactly $k$ apart from each other. Then we can see that different groups are independent, we can just multiply their results. For example, for $[2,4,6,20,20,22]$ and $k=2$, we construct two groups $[2,4,6]$ and $[20,20,22]$ (here both 20 are included in the same group), and the final result is $5*5-1=24$.\n\nWithin the same group, we use a simple DP to calculate the number of beautiful subsets. For the group $g$, We define $dp[0][j]$ to be the number of beautiful subsets within the group, up to $g[j]$, with the constraint that $g[j]$ is not included, and define $dp[1][j]$ to be the same amount, but instead $g[j]$ is included. Then the following transition follows:\n\n$$dp[0][j] = dp[0][j - 1] + dp[1][j - 1]$$\n\n$$dp[1][j] = (2 ^ {count(g[j])} - 1)dp[0][j - 1]$$\n\nwhere $count(g[j])$ is the number of occurrences of $g[j]$ in the array.\n\nFinally, the number of beutiful subsets for group $g$ is $dp[0][g.size() - 1] + dp[1][g.size() - 1]$. And the final result is the product of number of beutiful subsets different groups -1.\n\n# Complexity\n- Time complexity:\n$O(nlogn)$\n\n- Space complexity:\n$O(n)$\n\n# Code\n```\nclass Solution {\npublic:\n    int beautifulSubsets(vector<int>& nums, int k) {\n        int n = nums.size();\n        sort(nums.begin(), nums.end());\n        unordered_map<int, int> group;  // map each num to a group, numbers within each group are k apart\n        unordered_map<int, int> count_occ;  // count the number of occurrences of each number\n        vector<vector<int>> group_members;\n        for (int num: nums){\n            if (group.find(num - k) != group.end() || group.find(num) != group.end()){\n                if (group.find(num) == group.end()){  // consider the case that this number has appeared before\n                    group_members[group[num - k]].push_back(num);\n                    group[num] = group[num - k];\n                }\n            } else {  // create a new group\n                group[num] = group_members.size();\n                group_members.push_back({num});\n            }\n            ++count_occ[num];\n        }\n        long long res = 1;\n        for (vector<int>& members: group_members){\n            int group_size = members.size();\n            vector<vector<int>> dp(2, vector<int>(group_size));\n            // dp[0][j] is the number of beautiful subsets within the group, up to members[j], excluding members[j]\n            // dp[1][j] is the same quantity, including members[j]\n            dp[0][0] = 1;\n            dp[1][0] = (1 << count_occ[members[0]]) - 1;\n            for (int i = 1; i < group_size; ++i){\n                dp[0][i] = dp[0][i - 1] + dp[1][i - 1];\n                dp[1][i] = ((1 << count_occ[members[i]]) - 1) * dp[0][i - 1];\n            }\n            res *= dp[0][group_size - 1] + dp[1][group_size - 1];\n        }\n        return res - 1;  // -1 because we want non-empty subsets\n    }\n};\n```
['C++']