C# Solution for The Number of Beautiful Subsets Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is to count all \u201Cbeautiful\u201D subsets of an array, where a subset i
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is to count all \u201Cbeautiful\u201D subsets of an array, where a subset is considered beautiful if it does not contain any two elements whose absolute difference is equal to k. The solution uses a backtracking approach to explore all possible subsets, checking dynamically if the subset remains beautiful as elements are added.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tSorting the Array: Sorting helps in managing the subset generation in a structured way and facilitates easier handling of duplicates.\n2.\tBacktracking with State Tracking:\n\t\u2022\tFunction Definition: A recursive function CountBeautifulSubsets is used to explore subsets. The function takes the current index, the current subset, and a set to track the elements included so far.\n\t\u2022\tBase Case: If the current index reaches the end of the array, it checks if the current subset is non-empty and returns 1 (counting it as a valid subset) or 0 (if empty).\n\t\u2022\tRecursive Case:\n\t\u2022\tExclude Current Element: The function calls itself without including the current element.\n\t\u2022\tInclude Current Element: Before including the current element, it checks if including this element would violate the beautiful condition by checking the set for num - k or num + k. If valid, it includes the element, recurses, and then backtracks by removing the element.\n\t\u2022\tAccumulation: The counts from including and excluding the current element are accumulated to get the total count of beautiful subsets.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of this approach is O(2^n), where n is the length of the array:\n\n\u2022\tEach element has two choices (include or exclude), leading to 2^n possible subsets.\n\u2022\tThe check for the beautiful condition (set operations) takes O(1) on average due to the use of a hash set.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is O(n):\n\n\u2022\tThe recursion stack can go up to n levels deep in the worst case.\n\u2022\tThe space used for the current subset and the set of seen elements is proportional to n.\n\n# Code\n```\npublic class Solution {\n    public int BeautifulSubsets(int[] nums, int k) {\n        Array.Sort(nums);\n        return CountBeautifulSubsets(nums, k, 0, new List<int>(), new HashSet<int>());\n    }\n\n    private int CountBeautifulSubsets(int[] nums, int k, int index, List<int> currentSubset, HashSet<int> seen) {\n        if (index == nums.Length) {\n            return currentSubset.Count > 0 ? 1 : 0;\n        }\n\n        int count = 0;\n\n        // Case 1: Exclude current element and move to next element\n        count += CountBeautifulSubsets(nums, k, index + 1, currentSubset, seen);\n\n        // Case 2: Include current element if it does not violate the beautiful condition\n        int currentElement = nums[index];\n        if (!seen.Contains(currentElement - k) && !seen.Contains(currentElement + k)) {\n            currentSubset.Add(currentElement);\n            seen.Add(currentElement);\n            count += CountBeautifulSubsets(nums, k, index + 1, currentSubset, seen);\n            currentSubset.RemoveAt(currentSubset.Count - 1);\n            seen.Remove(currentElement);\n        }\n\n        return count;\n    }\n}\n```
['C#']