Java Solution for The Number of Beautiful Subsets Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe main idea is to explore all possible subsets of the given array nums and count thos
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe main idea is to explore all possible subsets of the given array nums and count those that satisfy the condition of being \u201Cbeautiful.\u201D A subset is considered beautiful if it doesn\u2019t contain any two elements whose absolute difference is equal to k.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tBitmasking: Utilize bitmasking to generate all possible subsets of the array. Each bitmask represents a subset where each bit indicates whether the corresponding element in the array is included in the subset.\n2.\tSubset Generation: For each bitmask, generate the corresponding subset by checking which bits are set.\n3.\tCheck Beautiful Condition: For each subset, use a set to ensure no two elements have an absolute difference equal to k.\n4.\tCount Beautiful Subsets: Increment the count if a subset satisfies the beautiful condition.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\u2022\tSubset Generation: Generating all subsets takes O(2^n) because there are 2^n possible subsets for an array of length n.\n\u2022\tChecking Beautiful Condition: For each subset, the worst-case scenario involves checking each pair of elements in the subset. On average, each subset has about n/2 elements, leading to a complexity of O(n) for checking. Thus, the checking process across all subsets has a complexity of O(n . 2^n).\nOverall Time Complexity: O(n . 2^n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\u2022\tStorage for Subsets: Storing each subset temporarily requires O(n) space.\n\u2022\tAuxiliary Space: The HashSet used for checking the beautiful condition also requires O(n) space.\n\nOverall Space Complexity: O(n)\n\n# Code\n```\nclass Solution {\n    public int beautifulSubsets(int[] nums, int k) {\n        int n = nums.length;\n        int count = 0;\n        \n        // Iterate over all possible subsets using bitmasks\n        for (int mask = 1; mask < (1 << n); mask++) {\n            List<Integer> subset = new ArrayList<>();\n            for (int i = 0; i < n; i++) {\n                if ((mask & (1 << i)) != 0) {\n                    subset.add(nums[i]);\n                }\n            }\n            \n            if (isBeautiful(subset, k)) {\n                count++;\n            }\n        }\n        \n        return count;\n    }\n\n    private boolean isBeautiful(List<Integer> subset, int k) {\n        Set<Integer> seen = new HashSet<>();\n        for (int num : subset) {\n            if (seen.contains(num - k) || seen.contains(num + k)) {\n                return false;\n            }\n            seen.add(num);\n        }\n        return true;\n    }\n}\n```
['Java']