Backtracking-> k groups O(n+m) without hash table||3ms Beats 99.79%
Intuition\n Describe your first thoughts on how to solve this problem. \n3 approaches:\n1. backtracking\n2. Divide into k group according to $x \pmod{k}$ for $x
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n3 approaches:\n1. backtracking\n2. Divide into k group according to $x \\pmod{k}$ for $x \\in nums$ +DP\n3. dual DP version + optimized space for 2nd C++. No need for sorting, thanks to comments of @Sergei99. The TC is linear `O(n+m)` where `m=max(nums)-min(nums)+1`\n# Approach\n<!-- Describe your approach to solving the problem. -->\nAvoid of using  unordered_map, unordered_set, map & set. Even` m/n>=50`, the array version is still faster than the versions with more complex data structure.\n1. sorting\n2. Backtracking according `freq[x]`\n\n2nd approach uses dividing into k groups with DP\n\n3. Use 2D array `freq[r][i]` to count the frequencies for `x` where `[i, r] = div(x, k)`\n4.  Use a nested for-loop. Within the same group,  using take & skip argument to compute `cnt`. \n5.  exclude the empty set, so return `ans-1`\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(2^n)\\to O(n+m)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$O(1001)$\n# Code Backtracking\n```\nclass Solution {\npublic:\n    char freq[1001] = {0};\n    int cnt = 0, n;\n    void backtrack(int idx, vector<int>& nums, int k) {\n        if (idx==n) {\n            cnt++;\n            return;\n        }\n        backtrack(idx+1, nums, k); // skip current number\n        int x = nums[idx];\n        if ((x - k < 0 || freq[x - k] == 0) &&\n            (x + k > 1000 || freq[x + k] == 0)) {\n            freq[x]++;\n            backtrack(idx+1, nums, k); // include current number\n            freq[x]--;\n        }\n    }\n    int beautifulSubsets(vector<int>& nums, int k) {\n        n = nums.size();\n        sort(nums.begin(), nums.end());\n        backtrack(0, nums, k);\n        return --cnt; // No empty subset\n    }\n};\n\n```\n# C++ dividing into k groups + DP ||8ms Beats 95.87%\n\nThis code keep sorting; it can be modified furthermore!\n```\nclass Solution {\npublic:\n    static int beautifulSubsets(vector<int>& nums, const int k) {\n        const int n = nums.size();\n        sort(nums.begin(), nums.end());\n        const int M = nums.back();\n        const int q = (M + k) / k; // ceil((M+1)/k)\n        \n        // Initialize the frequency array\n        char freq[k][q+1];\n        memset(freq, 0, sizeof(freq));\n        \n        for (auto x : nums) {\n            auto [i, r] = div(x, k);\n            freq[r][i]++;\n        }\n        \n        int ans = 1; // Start with 1 fpr the product\n        int cnt[q+1];\n        for (int r = 0; r < k; r++) {\n            fill(cnt, cnt+(q+1), 1);\n        //    cnt[q] = 1;\n            \n            for (int i = q-1; i>=0; i--) {\n                int take = (1 << freq[r][i])-1;\n                if (i+1<q) take *= cnt[i+2];\n                else take *= cnt[i+1];\n                cnt[i] = cnt[i+1] + take; // skip=cnt[i+1]\n            }\n            \n            ans*= cnt[0];\n        }\n        \n        return ans-1; //exclude the empty set\n    }\n};\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n\n```\n# C++ dual DP with optimized space||3ms Beats 99.79%\nforward loop is faster than backward loop, so convert into its dual version, no array for `cnt`, but just use variables `take, curr, prev`!\nNo need for sorting, since 2d array `freq` is in use.\n```\nclass Solution {\npublic:\n    static int beautifulSubsets(vector<int>& nums, const int k) {\n        const int n = nums.size();\n        auto [x_min, x_max]=minmax_element(nums.cbegin(), nums.cend());\n        const int M = *x_max - *x_min + 1;\n        const int q = (M + k) / k; // ceil((M+1)/k)\n        \n        // Initialize the frequency array\n        char freq[k][q+1];\n        memset(freq, 0, sizeof(freq));\n        \n        for (auto x : nums) {\n            auto [i, r] = div(x-*x_min, k);\n            freq[r][i]++;\n        }\n        \n        int ans = 1; // Start with 1 fpr the product\n        for (int r = 0; r < k; r++) {\n            int prev = 1, curr = 1;\n            for (int i = 0; i < q; i++) {\n                int take = (1 << freq[r][i]) - 1;\n                if (i > 0) take *= prev;\n                else take *= curr;\n                prev = curr;\n                curr = curr + take;\n            }\n            ans *= curr;\n        }\n\n        \n        return ans-1; //exclude the empty set\n    }\n};\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['Dynamic Programming', 'Backtracking', 'Sorting', 'C++']