🔥 🔥 🔥 Easy to understand | Video explanation | Backtracking 🔥 🔥 🔥
Video Explanation of the Approach\n\nhttps://www.youtube.com/watch?v=ewbeeOvYUUg\n\n# Intuition\n- The problem "Beautiful Subsets" involves finding all subsets 
# Video Explanation of the Approach\n\nhttps://www.youtube.com/watch?v=ewbeeOvYUUg\n\n# Intuition\n- The problem "Beautiful Subsets" involves finding all subsets of a given list of integers nums such that for any two integers x and y in a subset, the absolute difference between x and y is not equal to a given integer k. The goal is to count the number of such subsets.\n\n# Approach\n**1. Subsets Generation:**\n\n- The idea is to generate all possible subsets of the given list nums.\nThe function explore is used to recursively generate subsets.\n\n**2. Constraints Check:**\n\n- When adding an element x to the current subset, it is checked if x+k or x\u2212k is already in the subset.\n\n- If either x+k or x\u2212k exists in the current subset, x cannot be added to maintain the condition \u2223\uD835\uDC65 \u2212 \uD835\uDC66\u2223 \u2260 \uD835\uDC58.\n\n**3. Backtracking:**\n\nIf x can be added, it is marked as visited, and the recursion continues.\nAfter exploring the subset including x, the algorithm backtracks by removing x from the current subset and continues exploring subsets without x.\n\n**4. Count of Subsets:**\n\nThe counter count is incremented whenever a valid subset is formed (including the empty subset).\nFinally, the count is adjusted by subtracting 1 to exclude the empty subset from the result.\n\n# Complexity\n- Time complexity:\nO(2^N)\n\n- Space complexity:\nO(N)\n\n# Code\n```Python []\nclass Solution:\n    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n        # nums = [2,4,6]\n        # k = 2\n        # [], [2], [4], [6], [2, 4], [2, 6], [4, 6], [2, 4, 6]\n        # [2], [4], [6], [2, 6] -> 4 ans\n        # SOLUTION\n        # num - k or n + k\n\n        count = 0\n        lenNums = len(nums)\n\n        def explore(index):\n            nonlocal count\n            if lenNums == index:\n                count += 1\n                return\n\n            num = nums[index]\n\n            if num - k not in visited and num + k not in visited:\n                visited[num] += 1\n                explore(index + 1)\n                visited[num] -= 1\n                if visited[num] == 0:\n                    del visited[num]\n\n            explore(index + 1)\n\n        visited = defaultdict(int)\n        explore(0)\n        return count - 1\n\n```\n```Java []\npublic class Solution {\n    private int count;\n    private Map<Integer, Integer> visited;\n\n    public Solution() {\n        this.count = 0;\n        this.visited = new HashMap<>();\n    }\n\n    public int beautifulSubsets(int[] nums, int k) {\n        explore(nums, k, 0);\n        return count - 1; // Subtract 1 to exclude the empty subset\n    }\n\n    private void explore(int[] nums, int k, int index) {\n        if (index == nums.length) {\n            count++;\n            return;\n        }\n\n        int num = nums[index];\n\n        if (!visited.containsKey(num - k) && !visited.containsKey(num + k)) {\n            visited.put(num, visited.getOrDefault(num, 0) + 1);\n            explore(nums, k, index + 1);\n            visited.put(num, visited.get(num) - 1);\n            if (visited.get(num) == 0) {\n                visited.remove(num);\n            }\n        }\n\n        explore(nums, k, index + 1);\n    }\n}\n```\n```Go []\nfunc beautifulSubsets(nums []int, k int) int {\n\tcount := 0\n\tlenNums := len(nums)\n\tvisited := make(map[int]int)\n\n\tvar explore func(index int)\n\texplore = func(index int) {\n\t\tif index == lenNums {\n\t\t\tcount++\n\t\t\treturn\n\t\t}\n\n\t\tnum := nums[index]\n\n\t\tif _, exists1 := visited[num-k]; !exists1 {\n\t\t\tif _, exists2 := visited[num+k]; !exists2 {\n\t\t\t\tvisited[num]++\n\t\t\t\texplore(index + 1)\n\t\t\t\tvisited[num]--\n\t\t\t\tif visited[num] == 0 {\n\t\t\t\t\tdelete(visited, num)\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\n\t\texplore(index + 1)\n\t}\n\n\texplore(0)\n\treturn count - 1 // Subtract 1 to exclude the empty subset\n}\n```\n```Kotlin []\nclass Solution {\n    private var count = 0\n    private val visited = mutableMapOf<Int, Int>()\n\n    fun beautifulSubsets(nums: IntArray, k: Int): Int {\n        count = 0\n        explore(nums, k, 0)\n        return count - 1 // Subtract 1 to exclude the empty subset\n    }\n\n    private fun explore(nums: IntArray, k: Int, index: Int) {\n        if (index == nums.size) {\n            count++\n            return\n        }\n\n        val num = nums[index]\n\n        if (!visited.containsKey(num - k) && !visited.containsKey(num + k)) {\n            visited[num] = visited.getOrDefault(num, 0) + 1\n            explore(nums, k, index + 1)\n            visited[num] = visited[num]!! - 1\n            if (visited[num] == 0) {\n                visited.remove(num)\n            }\n        }\n\n        explore(nums, k, index + 1)\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int beautifulSubsets(vector<int>& nums, int k) {\n        count = 0;\n        explore(nums, k, 0);\n        return count - 1; // Subtract 1 to exclude the empty subset\n    }\n\nprivate:\n    int count;\n    unordered_map<int, int> visited;\n\n    void explore(vector<int>& nums, int k, int index) {\n        if (index == nums.size()) {\n            count++;\n            return;\n        }\n\n        int num = nums[index];\n\n        if (visited.find(num - k) == visited.end() &&\n            visited.find(num + k) == visited.end()) {\n            visited[num]++;\n            explore(nums, k, index + 1);\n            visited[num]--;\n            if (visited[num] == 0) {\n                visited.erase(num);\n            }\n        }\n\n        explore(nums, k, index + 1);\n    }\n};\n```\n\n# Please upvote\n\n![DALL\xB7E 2024-05-22 20.34.12 - A vibrant and colorful illustration of an upvote icon. The icon is a bold, upward-pointing arrow with a slight 3D effect, giving it a sense of depth. .webp](https://assets.leetcode.com/users/images/ce5e4f98-f7f8-4d06-8422-57d8f906c16f_1716431670.3547242.webp)\n
['Backtracking', 'Depth-First Search', 'C++', 'Java', 'Go', 'Python3', 'Kotlin']