EASY|| STEP WISE IN DEPTH SOLUTION.
Intuition\n Describe your first thoughts on how to solve this problem. \nProblem:\n\n- You have an array of integers nums.\n- A subset of nums is considered bea
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n**Problem:**\n\n- You have an array of integers `nums`.\n- A subset of `nums` is considered beautiful if for every number `x` in the subset, either `x + k` or `x - k` is also present in the subset (where `k` is a constant value).\n- The code finds the total number of beautiful subsets that can be formed from `nums`.\n\n**Approach:**\n\n- The code employs backtracking with a hash map to keep track of encountered numbers and avoid redundant calculations.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n\n\n\n**Steps:**\n\n1. **Initialization:**\n   - `int ans = 0;`: Initializes a variable `ans` to store the total number of beautiful subsets found.\n   - `HashMap<Integer, Integer> hs = new HashMap<>();`: Creates a hash map `hs` to store the number of occurrences of each number encountered during the recursive exploration.\n   - `List<Integer> al = new ArrayList<>();`: Creates a list `al` to store the current subset being built during recursion.\n\n2. **Recursive Function (`findAns`):**\n   - `public void findAns(int[] nums, int i, int k, List<Integer> al, HashMap<Integer, Integer> hs) {`: This function recursively explores all possible subsets.\n     - `nums`: The original array of integers.\n     - `i`: The current index in `nums` to start exploring from.\n     - `k`: The constant value.\n     - `al`: The current subset being built.\n     - `hs`: The hash map to track number occurrences.\n   - `ans++;`: Increments `ans` to count the current subset (even if it might not be beautiful). This accounts for the empty set as well.\n   - Loop through remaining elements:\n     - `for (int j = i; j < nums.length; j++) {`: Iterates from `i` (to avoid duplicates) to the end of `nums` to explore all possible elements for the current subset.\n       - **Avoid Redundant Calculations:**\n         - `if (hs.containsKey(nums[j] + k) && hs.get(nums[j] + k) > 0) {`: Checks if `nums[j] + k` exists in `hs` with a count greater than 0. This indicates that `nums[j] + k` has already been included in a previous beautiful subset that included `nums[j]`. So, to avoid exploring redundant possibilities that would still not be beautiful, we `continue` to the next element.\n         - Similar logic applies for `nums[j] - k`.\n       - Add current element and update hash map:\n         - `hs.put(nums[j], hs.getOrDefault(nums[j], 0) + 1);`: Updates the count of `nums[j]` in the hash map (`hs`).\n         - `al.add(nums[j]);`: Adds the current element (`nums[j]`) to the current subset (`al`).\n       - Make recursive call:\n         - `findAns(nums, j + 1, k, al, hs);`: Makes a recursive call to explore further possibilities based on the current subset (`al`) with the next element (`j + 1`).\n       - Backtrack and remove element:\n         - `hs.put(nums[j], hs.get(nums[j]) - 1);`: Decrements the count of `nums[j]` in the hash map (`hs`) as we backtrack from this option.\n         - `al.remove(al.size() - 1);`: Removes the current element (`nums[j]`) from the current subset (`al`) for backtracking.\n\n**Overall, the code cleverly uses backtracking to explore all possible subsets while leveraging a hash map to efficiently track encountered numbers and avoid redundant calculations that wouldn\'t lead to beautiful subsets.**\n\n\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n**Time Complexity:**\n\n- In the worst case, the code explores all possible subsets, which can be exponential (O(2^n)) in the number of elements (`n`).\n- The use of the hash map for lookups and updates contributes to a factor of `n` within the loops.\n- However, the pruning of redundant calculations using the hash map can significantly improve performance in practice.\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n**Space Complexity:**\n\n- The space complexity is mainly due to the recursion stack and the hash map (`hs`).\n- In the worst case, the recursion depth can be `n` (number of elements), and the hash map can store up to `n` unique elements.\n- Therefore, the space complexity can be considered O(n).\n# Code\n```\nclass Solution {\n    int ans=0;\n    public int beautifulSubsets(int[] nums, int k) {\n        //Arrays.sort(nums);\n        HashMap<Integer,Integer> hs=new HashMap<>();\n        List<Integer> al=new ArrayList<>();\n        findAns(nums,0,k,al,hs);\n        return ans-1;\n    }\n\n    public void findAns(int[] nums, int i,int k,List<Integer> al,HashMap<Integer,Integer> hs){\n        ans++;\n\n        for(int j=i;j<nums.length;j++){\n            \n            if( hs.containsKey(nums[j]+k) && hs.get(nums[j]+k)>0){\n                continue;\n            }\n            if( hs.containsKey(nums[j]-k) && hs.get(nums[j]-k)>0) {\n                continue;\n            }\n            \n            hs.put(nums[j],hs.getOrDefault(nums[j],0)+1);\n            al.add(nums[j]);\n            findAns(nums,j+1,k,al,hs);\n            hs.put(nums[j],hs.get(nums[j])-1);\n            al.remove(al.size()-1);\n\n        }\n    }\n}\n```
['Backtracking', 'Java']