题目思路
指数DFS暴力枚举
算法1
(DFS暴力枚举) $O(2^n)$
时间复杂度 $O(2^n)$
参考文献
AcWing 92. 递归实现指数型枚举
C++ 代码
const int N = 1010;
class Solution
{
public:
int beautifulSubsets(vector<int> &nums, int k)
{
vector<int> cnt(3 * N, 0);
return dfs(nums, cnt, k, 0) - 1;
}
int dfs(vector<int> &nums, vector<int> &cnt, int k, int u)
{
int ans = 0;
if (u == nums.size())
{
return 1;
}
int x = nums[u];
if (cnt[x - k + N] == 0 && cnt[x + k + N] == 0)
{
cnt[x + N]++;
ans += dfs(nums, cnt, k, u + 1);
cnt[x + N]--;
}
ans += dfs(nums, cnt, k, u + 1);
return ans;
}
};
const int N = 1010;
class Solution
{
public:
int beautifulSubsets(vector<int> &nums, int k)
{
unordered_map<int, int> seen;
return dfs(nums, seen, k, 0) - 1;
}
int dfs(vector<int> &nums, unordered_map<int, int> &seen, int k, int u)
{
int ans = 0;
if(u == nums.size()) {
return 1;
}
int x = nums[u];
if(seen[x - k] == 0 && seen[x + k] == 0) {
seen[x]++;
ans += dfs(nums, seen, k, u + 1);
seen[x]--;
}
ans += dfs(nums, seen, k, u + 1);
return ans;
}
};