📚 Clear and concise | Recursion backtracking technique | Java solution 📚
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires us to find the number of beautiful subsets from an array of intege
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires us to find the number of beautiful subsets from an array of integers, where a subset is considered beautiful if for every pair of integers in the subset, the absolute difference between them is not equal to a given integer \n\uD835\uDC58\nk. This naturally suggests a backtracking approach where we explore all possible subsets and check if they satisfy the beautiful condition.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can use a backtracking method to explore all subsets of the given array nums. The idea is to recursively decide for each element whether to include it in the current subset or not. We maintain a set to keep track of the elements included in the current subset and ensure that no two elements in the subset have an absolute difference equal to \n\uD835\uDC58\nk.\n\n**Backtracking Function:**\n\nThe function backtrack(ind, set, nums, k) will be used to explore all subsets starting from index ind.\nAt each index, we have two choices: include the current element in the subset or exclude it.\nIf we include the current element, we need to ensure that the difference condition is satisfied. If it is, we add the element to the set, recursively call the backtracking function for the next index, and then backtrack by removing the element from the set.\nIf we exclude the current element, we simply move to the next index.\nThe function returns the sum of the results of both choices.\nSorting:\n\nSorting the array initially helps in managing the set and checking conditions efficiently.\nBeautiful Subsets Function:\n\nThe main function beautifulSubsets(nums, k) initializes an empty set, sorts the array, and starts the backtracking process from the first index.\n\n# Complexity\n\n- Time complexity: The time complexity is $$O(2^n)$$ because in the worst case, we explore all possible subsets of the array.\n\n- Space complexity: The space complexity is $$O(n)$$ due to the recursion stack and the set used to store elements of the current subset.\n\n# Code\n```\nclass Solution {\n\n    public int backtrack(int ind, Set<Integer> set, int[] nums, int k) {\n        if (ind == nums.length) {\n            return 0;\n        };\n\n        int notTaken = backtrack(ind+1, set, nums, k);\n        int taken = 0;\n        if (!set.contains(nums[ind] - k) && !set.contains(nums[ind] + k)) {\n            set.add(nums[ind]);\n            taken = 1 + backtrack(ind+1, set, nums, k);\n            set.remove(nums[ind]);\n        }\n\n        return taken + notTaken;\n    }\n\n    public int beautifulSubsets(int[] nums, int k) {\n        Set<Integer> set = new HashSet<>();\n        Arrays.sort(nums);\n        return backtrack(0, set, nums, k);\n    }\n}\n```
['Array', 'Backtracking', 'Sorting', 'Java']