Optimized and fully explained Recursive to Memoization Approach ✅✅
Intuition\n Describe your first thoughts on how to solve this problem. \nTo optimize the recursive code, we can leverage several techniques:\n\n1. Memoization: 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo optimize the recursive code, we can leverage several techniques:\n\n1. **Memoization:** Use memoization to store the results of previously computed states in the recursive function. This avoids redundant calculations and significantly speeds up the process.\n\n1. **Bitmasking:** Instead of using an unordered_map to keep track of used elements, we can use a bitmask to represent the subset. This makes state management more efficient and helps with faster lookups and updates.\n\n1. **Iterative approach:** Convert the recursive approach to an iterative one using dynamic programming, which often helps to reduce the overhead of recursive calls.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Memoization Table:** dp[idx][mask] stores the result of the function call dfs(idx, mask), where idx is the current index in the nums array and mask is the bitmask representing the elements included in the subset.\n\n1. **DFS with Memoization:** We use a lambda function dfs to recursively compute the number of beautiful subsets. For each element, we decide whether to include it in the subset or not.\n\n1. **Bitmask Check:** Before including an element in the subset, we check if it is valid by ensuring that no previously included element has a difference of k with the current element.\n\n1. **Base Case:** When idx reaches n, it means we have considered all elements, so we return 1 to count this subset.\n\n1. **Final Answer:** We start the DFS with an empty subset (mask = 0). The final result is the total number of subsets minus 1 to exclude the empty subset.\n\nThis approach optimizes the recursive calls and makes the algorithm more efficient by avoiding redundant calculations and unnecessary state management with an unordered map.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n1.\t**Number of Subsets:** For each element in the array, we have two choices: include it in the subset or not. Therefore, there are 2^n possible subsets for an array of size n.\n2.\t**Memoization Table:** The memoization table dp has dimensions \uD835\uDC5B\xD72^n, where n is the length of the input array and 2^n represents all possible bitmasks.\n3.\t**State Computation:** Each state dfs(idx, mask) involves checking the feasibility of including the current element, which requires iterating through all elements currently included in the subset. In the worst case, this iteration takes O(n) time.\n\nGiven the above, **the total time complexity is: O(n\xD72^n)**. This is because for each of the 2^n subsets, we might perform n operations to check the feasibility of including the current element.\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n1.\t**Memoization Table:** The memoization table dp stores results for all possible states, which requires O(n\xD72^n) space.\n2.\t**Recursive Call Stack:** The depth of the recursive calls is at most n, the length of the input array. This requires O(n) space for the call stack.\n\nThus, the total space complexity is dominated by the memoization table: **O(n\xD72^n)**\n\nThese complexities are high, which is expected given the problem involves generating and examining all possible subsets of the array. **However, the memoization significantly reduces the number of redundant computations compared to a naive recursive approach.**\n\n\n# Recursive Code\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```\n\n\n# Memoization Code\n```\nclass Solution {\npublic:\n    int beautifulSubsets(vector<int>& nums, int k) {\n        int n = nums.size();\n        // Memoization table\n        vector<vector<int>> dp(n + 1, vector<int>(1 << n, -1));\n\n        // Helper function for memoized DFS\n        function<int(int, int)> dfs = [&](int idx, int mask) {\n            if (idx == n) return 1;\n            if (dp[idx][mask] != -1) return dp[idx][mask];\n\n            int notTaken = dfs(idx + 1, mask);\n\n            bool canTake = true;\n            for (int j = 0; j < n; ++j) {\n                if ((mask & (1 << j)) && (abs(nums[idx] - nums[j]) == k)) {\n                    canTake = false;\n                    break;\n                }\n            }\n\n            int taken = 0;\n            if (canTake) {\n                taken = dfs(idx + 1, mask | (1 << idx));\n            }\n\n            return dp[idx][mask] = taken + notTaken;\n        };\n\n        // Start DFS with index 0 and an empty subset\n        int result = dfs(0, 0);\n        return result - 1; // Subtract 1 to exclude the empty subset\n    }\n};\n\n```
['Array', 'Dynamic Programming', 'Backtracking', 'C++']