[Visual Explain] [Beats 100% !!] Group, multiply, subtract 1, you get the answer
Intuition\n\nDivide the input into non-colliding groups where decisions can be made within each of the group, then multiply the number of decisions per group to
# Intuition\n\nDivide the input into non-colliding groups where decisions can be made within each of the group, then multiply the number of decisions per group together to get the total number of "beautiful subsets", and subtract 1 which represents the empty subset\n\n![CCFA3725-2AD8-4D76-96DE-29EBA65CD672.png](https://assets.leetcode.com/users/images/4b88d109-c1aa-4579-a08d-36adaf050245_1679199057.5717845.png)\n\n\n# Approach\n\n- For dividing the input into groups: sort the input, and keep track of each group. Because the input gets sorted, this step is straightforward\n\n- For calculating the number of decisions for each group: Actually the group size is the only thing that matters. Refer to the bubble in the illustration for the way to fill in the D.P. table.\n\n- No backtrack, no bitset\n\n# Complexity\n- Time complexity: `O(nlogn)` for sorting the input. `O(1)` for populating the D.P. table\n\n- Space complexity: `O(n)` for counting the groups\n\n# Code\n```\nmap<int, int> dp;\nclass Solution {\npublic:\n    int Get(int x) {\n        if (dp.find(x) != dp.end()) {\n            return dp[x];\n        }\n        int ret = 0;\n        vector<vector<int>> haha(x, vector<int>(x));\n        for (int i=1; i<=x; i++) {\n            for (int idx=0; idx<x; idx++) {\n                if (i == 1) {\n                    haha[0][idx] = 1;\n                    ret ++;\n                } else {\n                    int idx1 = idx - 2;\n                    if (idx1 >= 0) {\n                        for (int idx11 = idx1; idx11 >= 0; idx11--) {\n                            haha[i-1][idx] += haha[i-2][idx11];\n                        }\n                        ret += haha[i-1][idx];\n                    }\n                }\n                //printf("%d ", haha[i-1][idx]);\n            }\n            //printf("\\n");\n        }\n        ret ++;\n        dp[x] = ret;\n        return ret;\n    }\n    int beautifulSubsets(vector<int>& nums, int k) {\n        set<int> nums1, used;\n        for (int n : nums) {\n            nums1.insert(n);\n        }\n        \n        vector<int> groups;\n        vector<int> group_sizes;\n        \n        sort(nums.begin(), nums.end());\n        int N = int(nums.size());\n        for (int i=0; i<N; i++) {\n            int elt = nums[i];\n            bool done = false;\n            for (int j=0; j<groups.size(); j++) {\n                if (groups[j] + k == elt) {\n                    groups[j] = elt;\n                    group_sizes[j] ++;\n                    done = true;\n                    break;\n                }\n            }\n            if (!done) {\n                groups.push_back(elt);\n                group_sizes.push_back(1);\n            }\n        }\n        \n        int ret = 1;\n        \n        for (int i=0; i<groups.size(); i++) {\n            ret *= Get(group_sizes[i]);\n            printf("group %d, size %d, ret=%d\\n", groups[i], group_sizes[i], ret);\n        }\n        \n        ret--;\n        \n        return ret;\n    }\n};\n```
['C++']