[C++, Java, Python] Evolve Brute Force to DP | Explained 7 Approaches
For every element $x$, we have a choice to take or not take it to make the subset. So, maximum number of possible subsets can be $2^n$.\n\n---\n\n\u2714\uFE0F S
For every element $x$, we have a choice to take or not take it to make the subset. So, maximum number of possible subsets can be $2^n$.\n\n---\n\n***\u2714\uFE0F Solution - I (Recursion + Backtracking) [Accepted]***\n\nLet\'s say we have to decide to take or not take the element at index $i$. We can recursively make two calls, one for not taking it and another for taking it. Since, question says subset should be non-empty, $1$ is subtracted from final result.\n\nTo take the element at index $i$, the elements $nums[i] \\pm k$ should not be taken in the subset before. Frequency map can be made to keep the track of elements taken till now.\n\n```C++ []\nclass Solution {\nprivate:\n    int _beautifulSubsets(vector<int>& nums, int k, unordered_map<int, int>& freq, int i) {\n        if (i == nums.size()) { // base case\n            return 1;\n        }\n        int result = _beautifulSubsets(nums, k, freq, i + 1); // nums[i] not taken\n        if (!freq[nums[i] - k] && !freq[nums[i] + k]) { // check if we can take nums[i]\n            freq[nums[i]]++;\n            result += _beautifulSubsets(nums, k, freq, i + 1); // nums[i] taken\n            freq[nums[i]]--;\n        }\n        return result;\n    }\n    \npublic:\n    int beautifulSubsets(vector<int>& nums, int k) {\n        unordered_map<int, int> freq;\n        return _beautifulSubsets(nums, k, freq, 0) - 1; // -1 for empty subset\n    }\n};\n```\n```Java []\nclass Solution {\n    private HashMap<Integer, Integer> freq;\n\n    private int beautifulSubsets(int[] nums, int k, int i) {\n        if (i == nums.length) { // base case\n            return 1;\n        }\n        int result = beautifulSubsets(nums, k, i + 1); // nums[i] not taken\n        if (!freq.containsKey(nums[i] - k) && !freq.containsKey(nums[i] + k)) { // check if we can take nums[i]\n            freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);\n            result += beautifulSubsets(nums, k, i + 1); // nums[i] taken\n            freq.put(nums[i], freq.get(nums[i]) - 1);\n            if (freq.get(nums[i]) == 0) {\n                freq.remove(nums[i]);\n            }\n        }\n        return result;\n    }\n\n    public int beautifulSubsets(int[] nums, int k) {\n        freq = new HashMap<Integer, Integer>();\n        return beautifulSubsets(nums, k, 0) - 1; // -1 for empty subset\n    }\n}\n```\n```Python []\nclass Solution:\n    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n        freq = {}\n        def f(i: int) -> int:\n            if i == len(nums): # base case\n                return 1\n            result = f(i + 1) # nums[i] not taken\n            if not nums[i] - k in freq and not nums[i] + k in freq: # check if we can take nums[i]\n                freq[nums[i]] = freq.get(nums[i], 0) + 1\n                result += f(i + 1) # nums[i] taken\n                freq[nums[i]] -= 1\n                if freq[nums[i]] == 0:\n                    del freq[nums[i]]\n            return result\n        return f(0) - 1 # -1 for empty subset\n```\n\nSince, maximum no. of subsets can be $2^n$, time complexity will be $O(2^n)$.\nRecursion stack space and frequency map will make space complexity $O(n)$.\n\n- Time Complexity: $$O(2^n)$$\n- Space Complexity: $$O(n)$$\n\n---\n\n***\u2714\uFE0F Solution - II (Recursion + Backtracking) [Accepted]***\n\nSince time complexity is already $O(2^n)$, sorting the array beforehand, for $O(n \\log n)$, will not change it. Also, if we know that before the current index $i$, there were no larger elements, then we have to check just for the existence of $nums[i] - k$, and not for $nums[i] + k$. Therefore, we sort the array.\n\nTime/Space Complexities will be same as before but LeetCode\'s Online Judge shows difference of $1200 ms$ and $800 ms$, so I thought to mention it too, as number of operations will be less.\n\n```C++ []\nclass Solution {\nprivate:\n    int _beautifulSubsets(vector<int>& nums, int k, unordered_map<int, int>& freq, int i) {\n        if (i == nums.size()) { // base case\n            return 1;\n        }\n        int result = _beautifulSubsets(nums, k, freq, i + 1); // nums[i] not taken\n        if (!freq[nums[i] - k]) { // check if we can take nums[i]\n            freq[nums[i]]++;\n            result += _beautifulSubsets(nums, k, freq, i + 1); // nums[i] taken\n            freq[nums[i]]--;\n        }\n        return result;\n    }\n    \npublic:\n    int beautifulSubsets(vector<int>& nums, int k) {\n        unordered_map<int, int> freq;\n        sort(nums.begin(), nums.end());\n        return _beautifulSubsets(nums, k, freq, 0) - 1; // -1 for empty subset\n    }\n};\n```\n```Java []\nclass Solution {\n    private HashMap<Integer, Integer> freq;\n\n    private int beautifulSubsets(int[] nums, int k, int i) {\n        if (i == nums.length) { // base case\n            return 1;\n        }\n        int result = beautifulSubsets(nums, k, i + 1); // nums[i] not taken\n        if (!freq.containsKey(nums[i] - k)) { // check if we can take nums[i]\n            freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);\n            result += beautifulSubsets(nums, k, i + 1); // nums[i] taken\n            freq.put(nums[i], freq.get(nums[i]) - 1);\n            if (freq.get(nums[i]) == 0) {\n                freq.remove(nums[i]);\n            }\n        }\n        return result;\n    }\n\n    public int beautifulSubsets(int[] nums, int k) {\n        freq = new HashMap<Integer, Integer>();\n        Arrays.sort(nums);\n        return beautifulSubsets(nums, k, 0) - 1; // -1 for empty subset\n    }\n}\n```\n```Python []\nclass Solution:\n    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n        freq = {}\n        nums.sort()\n        def f(i: int) -> int:\n            if i == len(nums): # base case\n                return 1\n            result = f(i + 1) # nums[i] not taken\n            if not nums[i] - k in freq: # check if we can take nums[i]\n                freq[nums[i]] = freq.get(nums[i], 0) + 1\n                result += f(i + 1) # nums[i] taken\n                freq[nums[i]] -= 1\n                if freq[nums[i]] == 0:\n                    del freq[nums[i]]\n            return result\n        return f(0) - 1 # -1 for empty subset\n```\n\n- Time Complexity: $$O(2^n)$$\n- Space Complexity: $$O(n)$$\n\n---\n\n***\u2714\uFE0F Solution - III (Recursion Optimized) [Accepted]***\n\nIn the above approach, we are trying to make every possible subset. The reason why we can\'t directly return $2^n$ without going to every subset, is that we don\'t know how many of them will satisfy the condition of *beautiful*. But what if there are no elements in the array whose difference is $k$?\n\n**Example 1**\nSuppose $nums = [1, 3, 5, 7]$, $k = 1$. We have differences of $2, 4, 6$ but never $1$. So, if we knew this before, we could have directly returned $2^n - 1 = 15$, ($-1$ for empty subset) without actually going to every subset by backtracking.\n\n**Example 2**\nNow, suppose $nums = [1, 2, 3, 4]$, $k = 2$. Difference of $2$ can be made by $4-2$, and $3-1$. That means $[2, 4]$ can\'t be in the same subset. Also, $[1, 3]$ can\'t be in the same subset. So, how can we write the answer if we knew this before?\nWe have two sets,\n$s_1 = [1, 3]$\n$s_2 = [2, 4]$\nWe can calculate number of *beautiful* subsets for $s_1$ and $s_2$ separately because the choices in $s_1$ is independent of $s_2$ and vice versa. Let the answers be $f(s_1)$ and $f(s_2)$.\nFor final answer, we can multiply both of them because there is no pair $(x_1,x_2)$ such that $x_1 \\in s_1$, $x_2 \\in s_2$ and $|x_1-x_2| = k$.\n$f(nums) = f(s_1) \\times f(s_2) - 1$ ($-1$ for empty subset)\n\n**Example 3**\nSo, one thing we can do is to separate the given array into these subsets, such that there is no pair $(x_1,x_2)$, $x_1$ and $x_2$ belonging to different subsets and $|x_1-x_2| = k$.\nIn one subset, there will be elemenets of the form: $[x, x + k, x + 2k, ..., x + \\lambda k]$.\nIf we take $x$, then we can\'t take $x+k$, but can take $x+2k$ and so on.\nAll these elements have common remainder when divided by $k$. So we can make these subsets by separating on the basis of remainder ($\\mod k$ ).\nFor example, $nums = [1, 2, 3, 4, 5, 6]$, $k = 2$.\n- $s_1$ : $nums[i] \\enspace \\% \\enspace k = 0$ : $[2,4,6]$\n- $s_2$ : $nums[i] \\enspace \\% \\enspace k = 1$ : $[1,3,5]$\n\nNote that all $x+\\lambda k$ might not be available in $s_1$. For example, there might be a possibility where $x+k$ is not present in $nums$ at all so subset will look like $[x, x+2k, ...]$.\n\n**Example 4**\nNow, suppose $nums = [5, 5, 5, 7, 7, 11, 11]$, $k = 2$. We can\'t take $[5, 7]$ in the same subset. Representing $s_1$ in $\\{value: frequency\\}$ form\n$s_1 = [5: 3, 7: 2, 11: 2]$\nLet\'s say $f(i)$ calculates number of beautiful subsets in $s_1$ starting from index $i$. We want to calculate $f(0)$.\n\n- When $i = 0$, we are at $5$, there are two options, whether we skip it or take it. There are $2^3$ ways, out of which in $2^3-1=7$ ways, we take atleast one $5$, and one way where we skip $5$.\n$take_5=7$, $skip_5=1$\n- Now, next element at $i + 1$ is $7=5+2=5+k$, so we can\'t take it if we took $5$. Therefore, number of ways of taking $5$ will be $take_5 \\times f(i + 2)$.\n- Number of ways of skipping $5$ will be $skip_5 \\times f(i + 1)$.\n> $take_{s[i]} = 2 ^ {frequency(s[i])} - 1$\n$skip_{s[i]} = 1$\n$f(i) = take_{s[i]} \\times f(i + 2) + skip_{s[i]} \\times f(i + 1)$\n- $f(0) = 7.f(2) + 1.f(1)$\n- When $i=1$, we are at $7$, there are two options, $take_7=2^2-1=3$ and $skip_7=1$. Next element is $11 = 7 + 4 = 7 + 2k$, so we can take it even if we took $7$.\n> $f(i) = take_{s[i]} \\times f(i + 1) + skip_{s[i]} \\times f(i + 1)$\n- $f(1) = 3.f(2) + 1.f(2)$\n- When $i=2$, we are at $11$, there are two options, $take_{11}=2^2-1=3$ and $skip_{11}=1$. Next element is nothing. So we will denote this as base case $f(n)=1$.\n> $f(i) = take_{s[i]} \\times f(i + 1) + skip_{s[i]} \\times f(i + 1)$\n- $f(2)=3.f(3)+1.f(3)=3.1+1.1=4$\n- $f(1)=3.f(2)+1.f(2)=3.4+1.4=16$\n- $f(0)=7.f(2)+1.f(1)=7.4+1.16=44$\n- $answer=f(0)-1=43$\n\nNow, general recurrence relation for $f(i)$ will be\n\n$$\nf(i) = skip_{s[i]} \\times f(i + 1) + take_{s[i]} \\times\n\\begin{cases}\n    f(i + 2) & \\text{if } s[i + 1] - s[i] = k \\\\\n    f(i + 1) & \\text{otherwise}\n\\end{cases}\n$$\n\nSplit the array into different $s_i$\'s based on their remainder with $k$. Sort them and represent in $\\{value : frequency\\}$ form. Final answer will be:\n\n$$answer = \\Big(\\prod_i f_{s_i}(0)\\Big) - 1$$\n\n```C++ []\nclass Solution {\nprivate:\n    int beautifulSubsets(vector<pair<int, int>>& s, int n, int k, int i) {\n        if (i == n) {\n            return 1;\n        }\n        int skip = beautifulSubsets(s, n, k, i + 1); // 1 * f(i + 1)\n        int take = (1 << s[i].second) - 1; // take s[i]\n        if (i + 1 < n && s[i + 1].first - s[i].first == k) { // next number is s[i] + k\n            take *= beautifulSubsets(s, n, k, i + 2);\n        } else {\n            take *= beautifulSubsets(s, n, k, i + 1);\n        }\n        return skip + take;\n    }\n\npublic:\n    int beautifulSubsets(vector<int>& nums, int k) {\n        int result = 1;\n        map<int,     map<int,  int>> freq;\n        // {remainder : {num : frequency}}\n        // map is sorted based on num to get subset of form [x, x + k, x + 2k, ...]\n        for (int& x: nums) { // splitting subsets based on remainder and calculating frequency\n            freq[x % k][x]++;\n        }\n        for (auto& fr: freq) { // loop for s1, s2, ...\n            vector<pair<int, int>> s(fr.second.begin(), fr.second.end());\n            result *= beautifulSubsets(s, s.size(), k, 0); // f(s1) * f(s2) ...\n        }\n        return result - 1; // -1 for empty subset\n    }\n};\n```\n```Java []\nclass Solution {\n    int[][] s;\n\n    private int beautifulSubsets(int n, int k, int i) {\n        if (i == n) {\n            return 1;\n        }\n        int skip = beautifulSubsets(n, k, i + 1); // 1 * f(i + 1)\n        int take = (1 << s[i][1]) - 1; // take s[i]\n        if (i + 1 < n && s[i + 1][0] - s[i][0] == k) { // next number is s[i] + k\n            take *= beautifulSubsets(n, k, i + 2);\n        } else {\n            take *= beautifulSubsets(n, k, i + 1);\n        }\n        return skip + take;\n    }\n\n    public int beautifulSubsets(int[] nums, int k) {\n        int result = 1;\n        Map<Integer, Map<Integer, Integer>> freq = new TreeMap<>();\n        // {remainder : {num :    frequency}}\n        // map is sorted based on num to get subset of form [x, x + k, x + 2k, ...]\n        for (int x: nums) { // splitting subsets based on remainder and calculating frequency\n            Map<Integer, Integer> fr = freq.getOrDefault(x % k, new TreeMap<>());\n            fr.put(x, fr.getOrDefault(x, 0) + 1);\n            freq.put(x % k, fr);\n        }\n        for (Map<Integer, Integer> fr: freq.values()) { // loop for s1, s2, ...\n            s = fr.entrySet().stream()\n                  .map(e -> new int[]{e.getKey(), e.getValue()})\n                  .toArray(int[][]::new);\n            result *= beautifulSubsets(s.length, k, 0); // f(s1) * f(s2) ...\n        }\n        return result - 1; // -1 for empty subset\n    }\n}\n```\n```Python []\nclass Solution:\n    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n        result = 1\n        freq = defaultdict(collections.Counter)\n        # {remainder : {num : frequency}}\n        for x in nums:\n            freq[x % k][x] += 1\n        for fr in freq.values(): # loop for s1, s2, ...\n            s = sorted(fr.items())\n            def f(i: int) -> int:\n                if i == len(s):\n                    return 1\n                skip = f(i + 1) # 1 * f(i + 1)\n                take = 2 ** s[i][1] - 1 # take s[i]\n                if i + 1 < len(s) and s[i + 1][0] - s[i][0] == k: # next number is s[i] + k\n                    take *= f(i + 2)\n                else:\n                    take *= f(i + 1)\n                return skip + take\n            result *= f(0) # f(s1) * f(s2) ...\n        return result - 1 # -1 for empty subset\n```\n\nSince map is sorted, it is implemented by Self Balancing BST. Insert operation is $O(\\log n)$, it will take $O(n \\log n)$ to make map. There can be $k$ different remainders, meaning maximum $k$ subset splits.\nWorst case hits when remainder is same for all numbers (i.e., all comes in same subset $s_1$) and no number is repeated ($frequency = 1$), time is still $O(2^n)$.\n\n- Time Complexity: $$O(n \\log n + 2^n) = O(2^n)$$\n- Space Complexity: $$O(n + k)$$\n\n---\n\n***\u2714\uFE0F Solution - IV (DP: Recursion + Memoization) [Accepted]***\n\n$f(i)$ calculates number of beautiful subsets in $s$ starting from index $i$. Memoize the function $f(i)$.\n\n```C++ []\nclass Solution {\nprivate:\n    int beautifulSubsets(vector<pair<int, int>>& s, int n, int k, int i, vector<int>& count) {\n        if (i == n) {\n            return 1;\n        }\n        if (count[i] != -1) {\n            return count[i];\n        }\n        int skip = beautifulSubsets(s, n, k, i + 1, count);\n        int take = (1 << s[i].second) - 1;\n        if (i + 1 < n && s[i + 1].first - s[i].first == k) {\n            take *= beautifulSubsets(s, n, k, i + 2, count);\n        } else {\n            take *= beautifulSubsets(s, n, k, i + 1, count);\n        }\n        return count[i] = skip + take;\n    }\n\npublic:\n    int beautifulSubsets(vector<int>& nums, int k) {\n        int result = 1;\n        map<int, map<int, int>> freq;\n        for (int& x: nums) {\n            freq[x % k][x]++;\n        }\n        for (auto& fr: freq) {\n            vector<pair<int, int>> s(fr.second.begin(), fr.second.end());\n            vector<int> count(s.size(), -1);\n            result *= beautifulSubsets(s, s.size(), k, 0, count);\n        }\n        return result - 1;\n    }\n};\n```\n```Java []\nclass Solution {\n    int[][] s;\n    int[] count;\n\n    private int beautifulSubsets(int n, int k, int i) {\n        if (i == n) {\n            return 1;\n        }\n        if (count[i] != -1) {\n            return count[i];\n        }\n        int skip = beautifulSubsets(n, k, i + 1);\n        int take = (1 << s[i][1]) - 1;\n        if (i + 1 < n && s[i + 1][0] - s[i][0] == k) {\n            take *= beautifulSubsets(n, k, i + 2);\n        } else {\n            take *= beautifulSubsets(n, k, i + 1);\n        }\n        return count[i] = skip + take;\n    }\n\n    public int beautifulSubsets(int[] nums, int k) {\n        int result = 1;\n        Map<Integer, Map<Integer, Integer>> freq = new TreeMap<>();\n        for (int x: nums) {\n            Map<Integer, Integer> fr = freq.getOrDefault(x % k, new TreeMap<>());\n            fr.put(x, fr.getOrDefault(x, 0) + 1);\n            freq.put(x % k, fr);\n        }\n        for (Map<Integer, Integer> fr: freq.values()) {\n            s = fr.entrySet().stream()\n                  .map(e -> new int[]{e.getKey(), e.getValue()})\n                  .toArray(int[][]::new);\n            count = new int[fr.size()];\n            Arrays.fill(count, -1);\n            result *= beautifulSubsets(s.length, k, 0);\n        }\n        return result - 1;\n    }\n}\n```\n```Python []\nclass Solution:\n    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n        result = 1\n        freq = defaultdict(collections.Counter)\n        for x in nums:\n            freq[x % k][x] += 1\n        for fr in freq.values():\n            s = sorted(fr.items())\n            @cache\n            def f(i: int) -> int:\n                if i == len(s):\n                    return 1\n                skip = f(i + 1)\n                take = 2 ** s[i][1] - 1\n                if i + 1 < len(s) and s[i + 1][0] - s[i][0] == k:\n                    take *= f(i + 2)\n                else:\n                    take *= f(i + 1)\n                return skip + take\n            result *= f(0)\n        return result - 1\n```\n\nMaking map is still $O(n \\log n)$. Calculating answer for one subset will be equal to number of states in DP which makes it $O(n)$.\n\n- Time Complexity: $$O(n \\log n + n) = O(n \\log n)$$\n- Space Complexity: $$O(n + k)$$\n\n---\n\n***\u2714\uFE0F Solution - V (Iterative DP) [Accepted]***\n\nChanging recursion to iteration. To calculate $f(i)$, we need to know $f(i + 1)$ and $f(i + 2)$. So DP should be filled right to left.\n\n```C++ []\nclass Solution {\npublic:\n    int beautifulSubsets(vector<int>& nums, int k) {\n        int result = 1;\n        map<int, map<int, int>> freq;\n        for (int& x: nums) {\n            freq[x % k][x]++;\n        }\n        for (auto& fr: freq) {\n            int n = fr.second.size();\n            vector<pair<int, int>> s(fr.second.begin(), fr.second.end());\n            vector<int> count(n + 1);\n            count[n] = 1;\n            for (int i = n - 1; i >= 0; i--) {\n                int skip = count[i + 1];\n                int take = (1 << s[i].second) - 1;\n                if (i + 1 < n && s[i + 1].first - s[i].first == k) {\n                    take *= count[i + 2];\n                } else {\n                    take *= count[i + 1];\n                }\n                count[i] = skip + take;\n            }\n            result *= count[0];\n        }\n        return result - 1;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int beautifulSubsets(int[] nums, int k) {\n        int result = 1;\n        Map<Integer, Map<Integer, Integer>> freq = new TreeMap<>();\n        for (int x: nums) {\n            Map<Integer, Integer> fr = freq.getOrDefault(x % k, new TreeMap<>());\n            fr.put(x, fr.getOrDefault(x, 0) + 1);\n            freq.put(x % k, fr);\n        }\n        for (Map<Integer, Integer> fr: freq.values()) {\n            int n = fr.size();\n            int[][] s = fr.entrySet().stream()\n                          .map(e -> new int[]{e.getKey(), e.getValue()})\n                          .toArray(int[][]::new);\n            int[] count = new int[n + 1];\n            count[n] = 1;\n            for (int i = n - 1; i >= 0; i--) {\n                int skip = count[i + 1];\n                int take = (1 << s[i][1]) - 1;\n                if (i + 1 < n && s[i + 1][0] - s[i][0] == k) {\n                    take *= count[i + 2];\n                } else {\n                    take *= count[i + 1];\n                }\n                count[i] = skip + take;\n            }\n            result *= count[0];\n        }\n        return result - 1;\n    }\n}\n```\n```Python []\nclass Solution:\n    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n        result = 1\n        freq = defaultdict(collections.Counter)\n        for x in nums:\n            freq[x % k][x] += 1\n        for fr in freq.values():\n            n = len(fr)\n            s = sorted(fr.items())\n            count = [0] * (n + 1)\n            count[n] = 1\n            for i in range(n - 1, -1, -1):\n                skip = count[i + 1]\n                take = 2 ** s[i][1] - 1\n                if i + 1 < n and s[i + 1][0] - s[i][0] == k:\n                    take *= count[i + 2]\n                else:\n                    take *= count[i + 1]\n                count[i] = skip + take\n            result *= count[0]\n        return result - 1\n```\n\n- Time Complexity: $$O(n \\log n)$$\n- Space Complexity: $$O(n + k)$$\n\n---\n\n***\u2714\uFE0F Solution - VI (Iterative DP Space Optimized) [Accepted]***\n\nTo calculate $f(i)$, we only need $f(i + 1)$ and $f(i + 2)$.\nStoring $f(i + 3)$ onwards is useless.\n- $curr = f(i)$\n- $next_1 = f(i + 1)$\n- $next_2 = f(i + 2)$\n\n```C++ []\nclass Solution {\npublic:\n    int beautifulSubsets(vector<int>& nums, int k) {\n        int result = 1;\n        map<int, map<int, int>> freq;\n        for (int& x: nums) {\n            freq[x % k][x]++;\n        }\n        for (auto& fr: freq) {\n            int n = fr.second.size(), curr, next1 = 1, next2;\n            vector<pair<int, int>> s(fr.second.begin(), fr.second.end());\n            for (int i = n - 1; i >= 0; i--) {\n                int skip = next1;\n                int take = (1 << s[i].second) - 1;\n                if (i + 1 < n && s[i + 1].first - s[i].first == k) {\n                    take *= next2;\n                } else {\n                    take *= next1;\n                }\n                curr = skip + take;\n                next2 = next1; next1 = curr;\n            }\n            result *= curr;\n        }\n        return result - 1;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int beautifulSubsets(int[] nums, int k) {\n        int result = 1;\n        Map<Integer, Map<Integer, Integer>> freq = new TreeMap<>();\n        for (int x: nums) {\n            Map<Integer, Integer> fr = freq.getOrDefault(x % k, new TreeMap<>());\n            fr.put(x, fr.getOrDefault(x, 0) + 1);\n            freq.put(x % k, fr);\n        }\n        for (Map<Integer, Integer> fr: freq.values()) {\n            int n = fr.size(), curr = 1, next1 = 1, next2 = 0;\n            int[][] s = fr.entrySet().stream()\n                          .map(e -> new int[]{e.getKey(), e.getValue()})\n                          .toArray(int[][]::new);\n            for (int i = n - 1; i >= 0; i--) {\n                int skip = next1;\n                int take = (1 << s[i][1]) - 1;\n                if (i + 1 < n && s[i + 1][0] - s[i][0] == k) {\n                    take *= next2;\n                } else {\n                    take *= next1;\n                }\n                curr = skip + take;\n                next2 = next1; next1 = curr;\n            }\n            result *= curr;\n        }\n        return result - 1;\n    }\n}\n```\n```Python []\nclass Solution:\n    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n        result = 1\n        freq = defaultdict(collections.Counter)\n        for x in nums:\n            freq[x % k][x] += 1\n        for fr in freq.values():\n            n, curr, next1, next2 = len(fr), 1, 1, 0\n            s = sorted(fr.items())\n            for i in range(n - 1, -1, -1):\n                skip = next1\n                take = 2 ** s[i][1] - 1\n                if i + 1 < n and s[i + 1][0] - s[i][0] == k:\n                    take *= next2\n                else:\n                    take *= next1\n                curr = skip + take\n                next2, next1 = next1, curr\n            result *= curr\n        return result - 1\n```\n\n- Time Complexity: $$O(n \\log n)$$\n- Space Complexity: $$O(n + k)$$\n\n---\n\n***\u2714\uFE0F Solution - VII (Iterative DP: Forward) [Accepted]***\n\nIn previous approaches, we were calculating in reverse direction (right to left) of $s$. Due to this, we needed to convert sorted map to array first. It can be avoided if we traverse left to right.\n\n```C++ []\nclass Solution {\npublic:\n    int beautifulSubsets(vector<int>& nums, int k) {\n        int result = 1;\n        map<int, map<int, int>> freq;\n        for (int& x: nums) {\n            freq[x % k][x]++;\n        }\n        for (auto& fr: freq) {\n            int prevNum = -k, prev2, prev1 = 1, curr;\n            for (auto& [num, f]: fr.second) {\n                int skip = prev1;\n                int take = ((1 << f) - 1) * (num - prevNum == k ? prev2 : prev1);\n                curr = skip + take;\n                prev2 = prev1; prev1 = curr;\n                prevNum = num;\n            }\n            result *= curr;\n        }\n        return result - 1;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int beautifulSubsets(int[] nums, int k) {\n        int result = 1;\n        Map<Integer, Map<Integer, Integer>> freq = new TreeMap<>();\n        for (int x: nums) {\n            Map<Integer, Integer> fr = freq.getOrDefault(x % k, new TreeMap<>());\n            fr.put(x, fr.getOrDefault(x, 0) + 1);\n            freq.put(x % k, fr);\n        }\n        for (Map<Integer, Integer> fr: freq.values()) {\n            int prevNum = -k, prev2 = 0, prev1 = 1, curr = 1;\n            for (Map.Entry<Integer, Integer> entry: fr.entrySet()) {\n                int num = entry.getKey(), f = entry.getValue();\n                int skip = prev1;\n                int take = ((1 << f) - 1) * (num - prevNum == k ? prev2 : prev1);\n                curr = skip + take;\n                prev2 = prev1; prev1 = curr;\n                prevNum = num;\n            }\n            result *= curr;\n        }\n        return result - 1;\n    }\n}\n```\n```Python []\nclass Solution:\n    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n        result = 1\n        freq = defaultdict(collections.Counter)\n        for x in nums:\n            freq[x % k][x] += 1\n        for fr in freq.values():\n            prevNum, curr, prev1, prev2 = -k, 1, 1, 0\n            for num in sorted(fr):\n                skip = prev1\n                take = (2 ** fr[num] - 1) * (prev2 if num - prevNum == k else prev1)\n                curr = skip + take\n                prev2, prev1 = prev1, curr\n                prevNum = num\n            result *= curr\n        return result - 1\n```\n\n- Time Complexity: $O(n \\log n)$\n- Space Complexity: $O(n + k)$\n\n---\n\nFor any mistakes / suggestions / questions, please do comment below \uD83D\uDC47\nUpvote if helps!
['Dynamic Programming', 'C++', 'Java', 'Python3']