Highly Detailed Explanation || 2 Methods Explained
Approach - 1\n\nLet\'s understand with an example, \n\nInput: nums = [2,4,6], k = 2\nOutput: 4\n\nIn this example of nums, we have 2,4,6 how many subsets we can
**Approach - 1**\n\nLet\'s understand with an example, \n```\nInput: nums = [2,4,6], k = 2\nOutput: 4\n```\nIn this example of nums, we have **2,4,6** how many subsets we can make. To make a subset, either we have to choose an element or not to choose an element!\nIn this, how many possible subsets are over here.\n```\n2^3\n```\nWhich means **choose** 2 or **not choose** 2, **choose** 4 or **not choose** 4, **choose** 6 or **not choose** 6\n```\n2 x 2 x 2 => 8\n```\nThus, no of possible subsets are 8\n\nBut, **no of beautiful subsets are what?**\nLet\'s see\n```\n{ } X // We don\'t want empty\n{2} \u2714\uFE0F // It\'s only one element, doesn\'t have any other element such that it\'s difference is 2 i.e. K\n{4} \u2714\uFE0F // It\'s only one element\n{6} \u2714\uFE0F // It\'s only one element\n{2, 6} \u2714\uFE0F // We can have, thus the difference isn\'t equals to K\n{2, 4} X // Diff. is equals to K\n{4, 6} X // Diff. is equals to K\n```\n\nNow, let\'s look at the constraints, as you see that **nums.length** is very less, i.e. `1 <= nums.length <= 20` means array length is small.\nSo, firstly I can try **BRUTE-FORCE**, because to make this subsets, I will require O(2^3) times i.e. **O(2^N)**, so my only thing is remain to check that particular subset which I made is good or not, which means a subset is made and how many subsets can be there i.e. `10^6 = O(2^N)` and for each subset we have to check okay, whether it is beautiful or not. And how to check beauty, if element **j - i** these will be 2 pointers, **i** will start from index 0 and **j** will start from index 1, so if **j - i == k** then it\'s not a beautifull subset and if it\'s not, then I will check for **i + 2** with the rest of the remaining front elements, unless it will be just O(N^2) to one subset, is it good or not.\n\nUltimately it will be` O(N^2 + 2^N)` which can work. \n\nBut we can also think of better thing, rather than making a subset and saying if it is good or not. **How about,** only making a good subset!\n\nSo, here we will only generate **beautifull subsets**, thus the part we need to check, okay if thats subset beautifull or not! That is just removed. So, it will `O(2^N)`, but **How to actually generate, Only beautifull subsets**. So, firstly we are about to generate a subset, we going to have 2 options. \nLet\'s say I have make half a subset and I\'m landing at an index **i**, now I will think shall I put in my existing subset or not.\n\nWhen we generate a subset we have 2 options, take it or not! Similarly, when we generate a beautifull subset we have one **additional option** (or can say additional condition), that is it **even possible to take it**. If it is YES, I will take it, if it is NO, then I will not take it.\nSom in the subset condition we have, we just add a small condition! And whats that small condition, is it even possible to take it!\n\n**Let\'s understand with an example,**\n```\nnums = [1, 2, 4, 5, 7, 10]\nk = 3\n```\n![image](https://assets.leetcode.com/users/images/e71f2d4e-5dfd-4ac6-b3dc-e819273d7d17_1716425821.500561.png)\n* What I showed is, lets say at any mid condition, which means at any point of time, I was able to get **1 and 4**\n* Now, I\'m standing at **5**, I have 2 options in mind, can I take it or I can\'t\n* If I take it, I have to ask myself is it even possible to take it, if we take **5** then it shoudn\'t be colliding with some of the elements inside. As you know, the existing was **1 and 4**, and if we adding **5**, so **5 - 4 = 1**, it\'s good and **5 - 1 = 4**, it\'s also good. Which is not equals to **k**. So, we had an option to take it.\n* But again we have to check, if it has option to take it or not and it says **YES**, then take it.\n* If we not take it, ignore it and move to the next **7**\n\n![image](https://assets.leetcode.com/users/images/981fec61-bb01-4822-9471-a5795483c439_1716426386.4292188.png)\n* Similar, in this case we have two option, firstly we have to ask is it even possile to take it. And it\'s **NO** , because we have **1, 2, 4** and if we take **5** then **5 - 2 = 3** and this is our **k**, so it means that although we want to take it, but we can\'t. So just move on to **7**\n* And it\'s not take it, it\'s exactly same just move to **7**\n\nSo, it is just that. In a normal subset condition, which is added one more condition two, if we want take it then this should be possible to take it. And how to check if it is possible to take it or not. It\'s simple let\'s say we are at element `a[i] - an element != k` or `[ai] - k != that element`\nAs if we see in **Case-2** when we choose to take it, `a[i]` i.e. **5** minus `k` i.e. **3** and diff is **2** but the **2** is present and we can check by using unorder hashmap, if it;s present map marked by **one** and if it\'s not, then marked as **zero**\n\nNow, lets look at it\'s code :\n\n**Pseudo Code**\n```\nfunction dfs(nums, idx, k, mp):\n    # Base case: if idx is equal to the size of nums, return 1 (a valid subset is found)\n    if idx == size of nums:\n        return 1\n\n    # Initialize taken to 0\n    taken = 0\n    \n    # Check if there are no elements in the map that are k units away from nums[idx]\n    if mp[nums[idx] - k] is 0 and mp[nums[idx] + k] is 0:\n        # Increment the count of nums[idx] in mp\n        mp[nums[idx]] += 1\n        \n        # Recursively call dfs with the next index and add the result to taken\n        taken = dfs(nums, idx + 1, k, mp)\n        \n        # Decrement the count of nums[idx] in mp\n        mp[nums[idx]] -= 1\n    \n    # Recursively call dfs with the next index without taking the current element\n    notTaken = dfs(nums, idx + 1, k, mp)\n    \n    # Return the sum of taken and notTaken\n    return taken + notTaken\n\nfunction beautifulSubsets(nums, k):\n    # Initialize mp as a map with default value 0\n    mp = map with default value 0\n    \n    # Call the dfs function starting from index 0\n    result = dfs(nums, 0, k, mp)\n    \n    # Subtract 1 from the result to exclude the empty subset\n    return result - 1\n```\n\n**C++**\n```\nclass Solution {\npublic:\n    int dfs(vector<int> &nums, int idx, int k, unordered_map<int, int> &mp) {\n    if(idx == nums.size()) return 1;\n\n    int taken = 0;\n    if(!mp[nums[idx] - k] && !mp[nums[idx] + k]) {\n        mp[nums[idx]]++;\n        taken = dfs(nums, idx + 1, k, mp);\n        mp[nums[idx]]--;\n    }\n    \n    int notTaken = dfs(nums, idx + 1, k, mp);\n    \n    return taken + notTaken;\n    }\n\n    int beautifulSubsets(vector<int> &nums, int k) {\n        unordered_map<int, int> mp;\n        int ans = dfs(nums, 0, k, mp);\n        return ans - 1;\n    }\n};\n```\n**JAVA**\n```\nclass Solution {\n    public int dfs(int[] nums, int idx, int k, HashMap<Integer, Integer> mp) {\n        if (idx == nums.length) return 1;\n\n        int taken = 0;\n        if (!mp.containsKey(nums[idx] - k) && !mp.containsKey(nums[idx] + k)) {\n            mp.put(nums[idx], mp.getOrDefault(nums[idx], 0) + 1);\n            taken = dfs(nums, idx + 1, k, mp);\n            mp.put(nums[idx], mp.get(nums[idx]) - 1);\n            if (mp.get(nums[idx]) == 0) {\n                mp.remove(nums[idx]);\n            }\n        }\n        \n        int notTaken = dfs(nums, idx + 1, k, mp);\n        \n        return taken + notTaken;\n    }\n\n    public int beautifulSubsets(int[] nums, int k) {\n        HashMap<Integer, Integer> mp = new HashMap<>();\n        int ans = dfs(nums, 0, k, mp);\n        return ans - 1;\n    }\n}\n```\n**PYTHON**\n```\nclass Solution:\n    def dfs(self, nums: List[int], idx: int, k: int, mp: defaultdict) -> int:\n        if idx == len(nums):\n            return 1\n\n        taken = 0\n        if mp[nums[idx] - k] == 0 and mp[nums[idx] + k] == 0:\n            mp[nums[idx]] += 1\n            taken = self.dfs(nums, idx + 1, k, mp)\n            mp[nums[idx]] -= 1\n        \n        notTaken = self.dfs(nums, idx + 1, k, mp)\n        \n        return taken + notTaken\n\n    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n        mp = defaultdict(int)\n        ans = self.dfs(nums, 0, k, mp)\n        return ans - 1\n```\n\n---\nComplexity Analysis\n\n---\n\n* **Time Complexity :-** BigO(Nx2^N)\n\n* **Space Complexity :-** BigO(N)\n\n---\n---\n**Approach - 2**\n\nBut did you notice one thing, in the previous example :\n```\nnums = [1, 2, 4, 5, 7, 10]\n```\nOur **5** was being hampered by **2** and our **4** was being hampered by **1**, why?\n**Because** `4 - k = 1` , `5 - k = 2` , `7 - k = 4` and `10 - k = 7`\n\nSo specific elements are hampering are being hampered by specific elements and it\'s for sure that our no **7** will never be hampered by **5**, it will always be hampered by **4** or something more then that.\n\nWhy so, because elements having the same **modulo** with **k**, will affect each other. So, I\'m just saying that, element having the same modulo can affect each other, but element having different module with **k** will never affect each other. Because for sure there difference will never be a multiple of **k**\n\nSo, we will do one thing. We will just mark what all element have the same modulo with **k**. Firstly we will get the modulo of **k**\n![image](https://assets.leetcode.com/users/images/931c37ba-ca74-4887-a7f9-e1e224f43b28_1716429022.2223036.png)\n* 1 % 3 = 1\n* 2 % 3 = \n\nFrom the diagram you see, the green once can affect each other, but they will never affect red ones and similarly red ones can affect the red ones only\n\nSo, by this we can make 2 groups. Green and Red. Which means okay, the **group-1** will affect each other and **group-2** will affect each other!\nBy anychance, if I get to know what all no of subsets can be make out of group one and what all subset can be made out of group two, then is it possible to reach to an answer, which means that in total number of subsets\n![image](https://assets.leetcode.com/users/images/8f995055-acea-4f11-b830-a3a620ea8f07_1716429511.631663.png)\n\nThe no of subsets we can make from **group-1** and no of subsets we can make from **group-2**, we can just multiply them and it will come out to be total number of subsets possible, which are **beautifull subsets**\n\nSee how,\n![image](https://assets.leetcode.com/users/images/bac6ab59-c3ca-4ba1-8681-a41639c904bc_1716430032.0321515.png)\n\nSo, as you see **group-1** can have subsets in total as **2 ^ 2** i.e. **4**, but the beautifull subset in **group-1** it can be :\n* empty one {}\n* {1}\n* {4}\n* and also {1, 4}, but this is not beautifull because **4-1 = 3**\n\nSo, in total number of beautifull subsets in **group-1 is 3** and number of beautifull subsets in **group-2 is 2**.\nSo, if we multiply them we will get **6 subsets**, which are `{}, {2}, {1}, {1, 2}, {4}, {4, 2}`, but in the starting as we have known, it can\'t have empty subset. Thus we will return, **whatsoever after multiplication - 1**\n\nBut, the problem occurs, how will you find number of beautifull subsets in one group?\nFirst see, how the beautifull subset looks like in **group-1**\n\n![image](https://assets.leetcode.com/users/images/8bbf6004-027d-4189-9e50-956f8ad2a767_1716431602.005041.png)\n\n\n* Firstly, we will have this empty one!\n* So, when I\'m moving I make sure my **i** path is include and I\'ll just look at my previous part!\n* Now, my **1** and uptill I have just got empty, so **1** is beautifull\n* Now, I landed on **4**, what all possibles I can have **4** and **4, 1**. But **4, 1** is not good\n* Now, landing at **7**, **7** can have **7**, **7 ,4**  but it\'s not beautifull and **7, 1**\n* Now, once I\'m at **10**, we can have **10**, **10, 7** is not good **10, 7, 4** is also not good, **10, 7, 1** is also not good, **10, 7, 4, 1** is also not good because. **10, 7** will never be good\n* If we choose **10, 4** it\'s good, but **10, 4, 1** is not good because **4 - 1**\n* and last **10, 1** it\'s also good one\n\nSo in last total as you can see that we had 7 subsets which are good! But in total we have to return 8, because empty one was not included. But final will be 7\n\n![image](https://assets.leetcode.com/users/images/9bf12667-eb9c-4ca1-af36-23b66ba82556_1716432314.339573.png)\nSo right now so far, if we not have **1**, we will have empty subset. But if we have **1**, we have **1**\n\nIf we move fwd. to 4\n![image](https://assets.leetcode.com/users/images/298d8318-56d3-4867-97e7-e00c1368e53d_1716432625.516811.png)\n\nNow let\'s move fwd. to 7\n![image](https://assets.leetcode.com/users/images/7e322c93-9bb5-450b-935e-6086ec0df08e_1716435401.9982882.png)\n\nand so on and so forth!!! I hope you have understand ladies and gentelmen!\n\nLet\'s code it UP:\n\n**C++**\n```\nclass Solution {\npublic:\n    int beautifulSubsets(vector<int>& nums, int k) {\n        unordered_map<int, vector<int>>mp;\n        for (auto el : nums){\n            mp[el%k].push_back(el);\n        }\n        \n        int ans = 1;\n        for(auto& [mod_cal, v] : mp){\n            sort(v.begin(), v.end());\n            map<int, int> mp2;\n            for (auto el : v) mp2[el]++;\n            \n            int prev_el = INT_MIN, prevNotTaken = 1, prevTaken = 0, nowNotTaken = 0, nowTaken = 0;\n            for(auto& [el, freq] : mp2){\n                int poss_subsets = pow(2, freq) - 1;\n                if(prev_el+k == el){\n                    nowNotTaken = prevNotTaken + prevTaken;\n                    nowTaken = prevNotTaken * poss_subsets;\n                }\n                else{\n                    nowNotTaken = prevNotTaken + prevTaken;\n                    nowTaken = (prevNotTaken + prevTaken) * poss_subsets;\n                }\n                \n                prevNotTaken = nowNotTaken;\n                prevTaken = nowTaken;\n                prev_el = el;\n            }\n            ans *= (nowNotTaken + nowTaken);                 \n        }\n        return ans - 1;\n    }\n};\n```\n\n---\nComplexity Analysis\n\n---\n\n* **Time Complexity :-** BigO(NlogN) + k\n\n* **Space Complexity :-** BigO(N)\n
['C', 'Python', 'Java']