O(2^N) C++ Backtracking Solution
Intuition\nThe list has a maximum of 20 elements. This allows us to generate all possible subsets and count the ones that are valid.\n\n### Approach\nRecurse th
### Intuition\nThe list has a maximum of 20 elements. This allows us to generate all possible subsets and count the ones that are valid.\n\n### Approach\nRecurse through the list building a subset by counting the current elements of the subset in a map. When reaching a number that can be added to the set while keeping it valid, add it and recurse. After backtracking, remove it and recurse again without the element. Once done subtract one from the result since the empty set doesn\u2019t meet requirements of a beautiful subset.\n\n### Complexity\nTime complexity:\n$O(2^N)$\n\nSpace complexity:\n$O(N)$\n\n### Code\n```\nclass Solution {\npublic:\n    // DFS Helper for recursing through list building a unique subset\n    void dfs(vector<int> &nums, int idx, int k, unordered_map<int, int> &mp, int &ans) {\n        // If we have reached the end of the list, count this unique subset\n        if(idx == nums.size()) ans++;\n        else {\n            // Otherwise, we need to recurse, if possible recurse taking this element for the subset\n            if(!mp[nums[idx] - k] && !mp[nums[idx] + k]) {\n                mp[nums[idx]]++;\n                dfs(nums, idx + 1, k, mp, ans);\n                mp[nums[idx]]--;\n            }\n            // Recurse without taking this element in the subset\n            dfs(nums, idx + 1, k, mp, ans);\n        }\n    }\n    \n    // O(2^N) Solution that generates all valid subsets and counts them in the result variable\n    int beautifulSubsets(vector<int>& nums, int k) {\n        // Initialize our result as 0\n        int ans = 0;\n        // Initialize a map for the count of elements in our current set\n        unordered_map<int, int> mp;\n        // DFS through the numbers array from index 0\n        dfs(nums, 0, k, mp, ans);\n        // Return all of the counted sets - 1 for the empty set\n        return ans - 1;\n    }\n};\n```
['Backtracking', 'Depth-First Search', 'Counting', 'C++']