[C++ / Go] Backtracking + Hash Map - O(2^n) time + O(n) space
Approach\n- Generate all possible subsets of the given array using a recursive backtracking method.\n- For each number in the array, it can either be included i
# Approach\n- Generate all possible subsets of the given array using a recursive backtracking method.\n- For each number in the array, it can either be included in the current subset or ignored.\n- A map is used to keep track of the numbers that have been chosen in the current subset.\n- Before including a number `num` in the subset, the algorithm checks that neither `num - k` nor `num + k` is already in the subset. \n    - Can sort the array first and just check for appearance of `num - k`.\n\n# Complexity\n- Time complexity: $O(2^n)$\n- Space complexity: $O(n)$\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    void backtrack(const vector<int>& nums, int k, unordered_map<int, int>& flag, int pos, int& res) {\n        if (pos == nums.size()) {\n            res++;\n            return;\n        }\n\n        backtrack(nums, k, flag, pos + 1, res);\n\n        int num = nums[pos];\n        if (!flag[num - k]) {\n            flag[num]++;\n            backtrack(nums, k, flag, pos + 1, res);\n            flag[num]--;\n        }\n    }\n\n    int beautifulSubsets(vector<int>& nums, int k) {\n        sort(nums.begin(), nums.end());\n        unordered_map<int, int> flag;\n        int res = 0;\n        backtrack(nums, k, flag, 0, res);\n        return res - 1;\n    }\n};\n```\n```Go []\nfunc backtrack(nums []int, k int, flag map[int]int, pos int, res *int) {\n\tif pos == len(nums) {\n\t\t*res++\n\t\treturn\n\t}\n\n\tbacktrack(nums, k, flag, pos + 1, res)\n\n\tnum := nums[pos]\n\tif flag[num - k] == 0 {\n\t\tflag[num]++\n\t\tbacktrack(nums, k, flag, pos + 1, res)\n\t\tflag[num]--\n\t}\n}\n\nfunc beautifulSubsets(nums []int, k int) int {\n    sort.Ints(nums)\n\tflag := make(map[int]int)\n\tres := 0\n\tbacktrack(nums, k, flag, 0, &res)\n\treturn res - 1\n}\n```
['Backtracking', 'Sorting', 'C++', 'Go']