C++ O(n) bottom up DP over k groups
Approach\nSee https://leetcode.com/problems/the-number-of-beautiful-subsets/solutions/5195870/easy-c-beats-100-with-explanation/?envType=daily-question&envId=20
# Approach\nSee https://leetcode.com/problems/the-number-of-beautiful-subsets/solutions/5195870/easy-c-beats-100-with-explanation/?envType=daily-question&envId=2024-05-23 which I was inspired by\n\n# Code\n```\nclass Solution {\npublic:\n    int beautifulSubsets(vector<int>& nums, int k) {\n        vector<int> counts(1001);\n        for(int i : nums) {\n            counts[i]++;\n        }\n\n        vector<int> DP_with(1001, 0), DP_without(1001, 1);\n        // iterate over residues\n        // bottom-up DP over quotiets\n        for (int res = 0; res < k; res++) {\n            // set up base case where q=0\n            if(counts[res]) {\n                DP_with[res] = (1 << counts[res]) - 1;\n            }\n\n            for (int q = 1; q <= 1000/k; q++) {\n                int n = q*k + res;\n                if (n > 1000) {\n                    break;\n                }\n                DP_without[n] = DP_with[n-k] + DP_without[n-k];\n                if(counts[n]) {\n                    DP_with[n] = ((1 << counts[n]) - 1) * DP_without[n-k];\n                }\n            }\n        }\n        \n        int result = 1;\n        for (int n = 1000; n > 1000-k; n--) {\n            result *= (DP_with[n] + DP_without[n]);\n        }\n        return result - 1; //exclude empty set\n    }\n};\n```
['C++']