O(n) simple DP
Intuition\nPut all the numbers in the same arithmetic progression of common difference k in a single group. We can process them together. The key idea is that w
# Intuition\nPut all the numbers in the same arithmetic progression of common difference k in a single group. We can process them together. The key idea is that we can only select non adjacent numbers in this arithmetic progression. The final answer is the product of number of ways to select number in each arithmetic progression minus 1 (the empty set).\n\n\n# Approach\n1. To get out all the arithmetic progressions, we put all the elements into hash map with the numbers as the key and the number of occurences as the value. Start from any key, we can check whether (key - k), (key - 2 * k), ..... are in the map. So that we get out the smallest key in this arithmetic progression that is in the hash map, let\'s call it x. Here x must be key - k * y for some y >= 0. Start from the number x, generate the arithmetic progressions as x, x + k, x + 2 * k, ...... and all of the numbers must be in the hashmap. Whenever we get one number, we delete it from the hashmap.\n\n2. Calculate the number of ways to select non adjacent numbers in this rithmetic progressions. This can be done by DP. Let be the number of ways to select the numbers from the first i numbers (indices from 0 to i - 1) in the arithmetic progression. We have\n\ndp[i] = dp[i - 1] + dp[i - 2] * (2 ^ num[i - 1] - 1) where num[i - 1] is the number of occurences of the number with index (i - 1).\nThis means to select number from the first i numbers, we can select number from the first (i - 1) numbers without the one indexed at (i - 1) or select the number from the first (i - 2) numbers with the one indexed at (i - 1). For the latter case, we need to select at least one from the num[i - 1] duplicated numbers (the numbers that are the same as the one indexed at i - 1).\n\nThe base cases are dp[0] = 1 (empty), dp[1] = 2 ^ num[0] (a single element). \n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    int beautifulSubsets(vector<int>& nums, int k) {\n        unordered_map<int, int> have;\n        for (int x : nums) {\n            ++have[x];\n        }\n        int r = 1;\n        while (!have.empty()) {\n            int x = have.begin()->first;\n            for (;have.count(x - k); x -=k)\n            ;\n            vector<int> dp = {1, 1 << have[x], 0};\n            have.erase(x);\n            int ind = 1;\n            for (x += k; have.count(x); x += k) {\n                ++ind;\n                dp[ind % 3] = dp[(ind - 1) % 3] + \n                (dp[(ind - 2) % 3] << have[x]) - dp[(ind - 2) % 3];\n                have.erase(x);\n            }\n            r *= dp[ind % 3];\n        }\n        return r - 1;\n    }\n};\n```
['C++']