📊Easy Approach with Explanation 💹🔰📊|| Beats 98% || 🚀 Beautiful Subsets
Intuition\nTo solve the problem of finding beautiful subsets, we need to systematically explore all possible subsets of the array nums. A subset is considered b
# Intuition\nTo solve the problem of finding beautiful subsets, we need to systematically explore all possible subsets of the array nums. A subset is considered beautiful if the absolute difference between any two elements in the subset is not equal to k. By using recursion and a HashMap to track the elements and their constraints, we can efficiently explore all subsets while maintaining the required conditions.\n\n# Approach\n1. Recursive Function: Define a recursive function solve that takes the current index, the array nums, a HashMap map to track element frequencies, and the value k.\n2. Base Case: If the current index reaches the end of the array, check if the subset formed is non-empty. If yes, return 1 (valid subset), otherwise return 0.\n3. Include Element: Check if the current element can be included in the subset without violating the beautiful subset condition. This is ensured by checking if map contains nums[index] + k or nums[index] - k.\n4. Exclude Element: Recursively call the function by excluding the current element.\n5. Combine Results: Sum the results of including and excluding the current element to get the total count of beautiful subsets.\n\n# Complexity\n- Time complexity:$$O(2^n)$$,where \uD835\uDC5B is the number of elements in nums, since we explore all subsets.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n)$$, due to the recursive call stack and the HashMap used for tracking elements.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n```JAVA []\nclass Solution {\n    // Helper function to count beautiful subsets\n    public int solve(int index, int[] nums, HashMap<Integer, Integer> map, int k) {\n        // Base case: if we reach the end of the array\n        if (index == nums.length) {\n            // If the map is not empty, return 1 (valid subset), else return 0\n            if (map.size() != 0) return 1;\n            return 0;\n        }\n\n        int include = 0;\n\n        // Check if the current element can be included\n        if (!map.containsKey(nums[index] + k) && !map.containsKey(nums[index] - k)) {\n            // Include the current element\n            map.put(nums[index], map.getOrDefault(nums[index], 0) + 1);\n            include = solve(index + 1, nums, map, k);\n            // Backtrack: remove the current element\n            map.put(nums[index], map.get(nums[index]) - 1);\n            if (map.get(nums[index]) == 0) map.remove(nums[index]);\n        }\n\n        // Exclude the current element\n        int exclude = solve(index + 1, nums, map, k);\n\n        // Return the sum of including and excluding the current element\n        return include + exclude;\n    }\n\n    public int beautifulSubsets(int[] nums, int k) {\n        HashMap<Integer, Integer> map = new HashMap<>();\n        // Start the recursion with the initial parameters\n        return solve(0, nums, map, k);\n    }\n}\n\n```\n```C++ []\n#include <vector>\n#include <unordered_map>\nusing namespace std;\n\nclass Solution {\npublic:\n    // Helper function to count beautiful subsets\n    int solve(int index, vector<int>& nums, unordered_map<int, int>& map, int k) {\n        // Base case: if we reach the end of the array\n        if (index == nums.size()) {\n            // If the map is not empty, return 1 (valid subset), else return 0\n            if (!map.empty()) return 1;\n            return 0;\n        }\n\n        int include = 0;\n\n        // Check if the current element can be included\n        if (map.find(nums[index] + k) == map.end() && map.find(nums[index] - k) == map.end()) {\n            // Include the current element\n            map[nums[index]]++;\n            include = solve(index + 1, nums, map, k);\n            // Backtrack: remove the current element\n            map[nums[index]]--;\n            if (map[nums[index]] == 0) map.erase(nums[index]);\n        }\n\n        // Exclude the current element\n        int exclude = solve(index + 1, nums, map, k);\n\n        // Return the sum of including and excluding the current element\n        return include + exclude;\n    }\n\n    int beautifulSubsets(vector<int>& nums, int k) {\n        unordered_map<int, int> map;\n        // Start the recursion with the initial parameters\n        return solve(0, nums, map, k);\n    }\n};\n\n```\n```Python []\nclass Solution:\n    def solve(self, index, nums, map, k):\n        # Base case: if we reach the end of the array\n        if index == len(nums):\n            # If the map is not empty, return 1 (valid subset), else return 0\n            if len(map) != 0:\n                return 1\n            return 0\n        \n        include = 0\n        \n        # Check if the current element can be included\n        if (nums[index] + k) not in map and (nums[index] - k) not in map:\n            # Include the current element\n            map[nums[index]] = map.get(nums[index], 0) + 1\n            include = self.solve(index + 1, nums, map, k)\n            # Backtrack: remove the current element\n            map[nums[index]] -= 1\n            if map[nums[index]] == 0:\n                del map[nums[index]]\n        \n        # Exclude the current element\n        exclude = self.solve(index + 1, nums, map, k)\n        \n        # Return the sum of including and excluding the current element\n        return include + exclude\n    \n    def beautifulSubsets(self, nums, k):\n        # Start the recursion with the initial parameters\n        return self.solve(0, nums, {}, k)\n\n```\n\nPlease UpVOTE for Anya Chan if you reach till here !! \n![image.png](https://assets.leetcode.com/users/images/b4a46600-e4dc-412e-8633-7820ca6a98f7_1716477313.887889.png)\n
['Backtracking', 'Recursion', 'Python', 'C++', 'Java', 'Python3']