Easy || Java || Backtracking || Fully Explained || Please Upvote
Intuition and Approach\n\nThe goal is to count all the subsets of the array nums that do not contain any two integers with an absolute difference equal to k. A 
### Intuition and Approach\n\nThe goal is to count all the subsets of the array `nums` that do not contain any two integers with an absolute difference equal to `k`. A brute-force approach would involve generating all subsets and then checking each one for the given condition, but this would be highly inefficient for larger arrays. Instead, a more efficient approach uses depth-first search (DFS) combined with a hashmap to keep track of the elements in the current subset and ensure the condition is maintained.\n\n### Approach\n\n1. **DFS Traversal**: We use a recursive DFS function to explore each element in `nums`. For each element, we have two choices: either include it in the current subset or exclude it.\n2. **Map to Track Validity**: A hashmap (`map`) keeps track of the elements in the current subset to quickly check if adding a new element would violate the "beautiful" condition.\n3. **Base Case**: If the index (`idx`) reaches the length of `nums`, we return 1, which means we have found a valid subset.\n4. **Include or Exclude Current Element**:\n   - **Include**: Before including an element `nums[idx]`, we check the hashmap to ensure no element in the current subset has an absolute difference of `k` with `nums[idx]`. If it\u2019s valid, we add it to the hashmap, recurse, and then backtrack by removing it.\n   - **Exclude**: Simply recurse without adding the current element.\n5. **Combine Results**: The total count of beautiful subsets is the sum of counts from including and excluding the current element.\n\n### Complexity\n\n- **Time Complexity**: $O(2^n)$\n  - Each element has two choices (include or exclude), leading to $2^n$ possible subsets. The DFS function is called recursively for each subset.\n- **Space Complexity**: $O(n)$\n  - The recursion stack can go as deep as the number of elements $n$. The hashmap\u2019s size can also grow up to $n$.\n\nThe provided solution effectively combines these ideas to count the beautiful subsets.\n\n### Code\n\nHere is the provided code with some additional comments for clarity:\n\n```java []\nclass Solution {\n    public int beautifulSubsets(int[] nums, int k) {\n        Map<Integer, Integer> map = new HashMap<>();\n        // Starting the DFS traversal from index 0\n        int ans = dfs(nums, 0, k, map);\n        // Subtract 1 to exclude the empty subset\n        return ans - 1;\n    }\n    \n    public int dfs(int[] nums, int idx, int k, Map<Integer, Integer> map) {\n        // Base case: If we have processed all elements\n        if (idx == nums.length) return 1;\n        \n        int taken = 0;\n        // Check if the current element can be taken\n        if (!map.containsKey(nums[idx] - k) && !map.containsKey(nums[idx] + k)) {\n            // Include the current element\n            map.put(nums[idx], map.getOrDefault(nums[idx], 0) + 1);\n            taken = dfs(nums, idx + 1, k, map);\n            // Backtrack: Remove the current element\n            map.put(nums[idx], map.get(nums[idx]) - 1);\n            if (map.get(nums[idx]) == 0) map.remove(nums[idx]);\n        }\n        \n        // Exclude the current element\n        int notTaken = dfs(nums, idx + 1, k, map);\n        \n        // Total beautiful subsets from this state\n        return taken + notTaken;\n    }\n}\n```\n\nThis solution effectively uses DFS and backtracking with a hashmap to count the number of beautiful subsets efficiently.\n\n![upvote.jpeg](https://assets.leetcode.com/users/images/97d6e45c-82c4-4403-b6df-85b29bf64dd5_1716478942.9973059.jpeg)\n
['Array', 'Backtracking', 'Recursion', 'Java']