Easy and Intuitive Hashmap+Recursion approach || C++ 💯
Beautiful Subsets\n\n## Problem Statement\nGiven an array nums of positive integers and a positive integer k, a subset of nums is beautiful if it does not conta
# Beautiful Subsets\n\n## Problem Statement\nGiven an array `nums` of positive integers and a positive integer `k`, a subset of `nums` is beautiful if it does not contain two integers with an absolute difference equal to `k`. Return the number of non-empty beautiful subsets of the array `nums`.\n\n## Intuition\nTo solve this problem, we need to explore all possible subsets of the array and count only those that do not contain any two elements with an absolute difference of `k`. This suggests a backtracking approach where we recursively decide whether to include or exclude each element and keep track of the current subset\'s validity.\n\n## Approach\n1. **Recursive Backtracking**: Use a recursive function `solve` to explore all subsets. At each step, decide whether to include the current element in the subset.\n2. **Frequency Map**: Use a frequency map to track the elements currently included in the subset. This helps efficiently check the absolute difference condition.\n3. **Backtracking**: Ensure to backtrack after exploring each decision (including or excluding an element) to restore the state for further exploration.\n\n### Detailed Steps\n1. Start with an empty subset and the first element of the array.\n2. For each element, decide to either:\n   - Exclude it and move to the next element.\n   - Include it only if it does not violate the beautiful subset condition (checked using the frequency map).\n3. Count each valid subset (non-empty) formed when reaching the end of the array.\n4. Subtract one from the final count to exclude the empty subset.\n\n## Complexity\n- **Time Complexity**: \\(O(2^n)\\)\n  - Each element has two choices: to be included or excluded, leading to \\(2^n\\) subsets.\n- **Space Complexity**: \\(O(n)\\)\n  - The recursion stack can go as deep as the number of elements \\(n\\).\n\n## Code\n```cpp\nclass Solution {\npublic:\n    void solve(vector<int>& nums, int index, int k, unordered_map<int, int>& freq, int& count) {\n        // Base case: if we\'ve considered all elements\n        if (index == nums.size()) {\n            count++;  // Every path to this point is a valid subset\n            return;\n        }\n\n        // Exclude the current element and move to the next\n        solve(nums, index + 1, k, freq, count);\n        \n        // Check if we can include nums[index] in the subset\n        bool canInclude = true;\n        if (freq[nums[index] - k] > 0 || freq[nums[index] + k] > 0) {\n            canInclude = false;\n        }\n\n        // Include the current element if it\'s valid\n        if (canInclude) {\n            freq[nums[index]]++;\n            solve(nums, index + 1, k, freq, count);\n            freq[nums[index]]--;  // Backtrack\n        }\n    }\n\n    int beautifulSubsets(vector<int>& nums, int k) {\n        unordered_map<int, int> freq;\n        int count = 0;\n        solve(nums, 0, k, freq, count);\n        return count - 1; // Subtract 1 to exclude the empty subset\n    }\n};\n
['Hash Table', 'Backtracking', 'Recursion', 'C++']