题目描述
给你一个由正整数组成的数组 nums
和一个 正 整数 k
。
如果 nums
的子集中,任意两个整数的绝对差均不等于 k
,则认为该子数组是一个 美丽 子集。
返回数组 nums
中 非空 且 美丽 的子集数目。
nums
的子集定义为:可以经由 nums
删除某些元素(也可能不删除)得到的一个数组。只有在删除元素时选择的索引不同的情况下,两个子集才会被视作是不同的子集。
样例
输入:nums = [2,4,6], k = 2
输出:4
解释:数组 nums 中的美丽子集有:[2], [4], [6], [2, 6]。
可以证明数组 [2,4,6] 中只存在 4 个美丽子集。
输入:nums = [1], k = 1
输出:1
解释:数组 nums 中的美丽数组有:[1]。
可以证明数组 [1] 中只存在 1 个美丽子集。
限制
1 <= nums.length <= 20
1 <= nums[i], k <= 1000
算法
(递归回溯) $O(m + 2^n)$
- 递归枚举每个数字选还是不选。定义长度为 $m$ 的数组,用于记录每个数字标记的次数,其中 $m$ 为最大的数字。
- 如果当前选这个数字 $x$,需要满足这个数字没被标记过,且选了之后,标记 $x - k$ 和 $x + k$。
时间复杂度
- 初始化标记数组的时间复杂度为 $O(m)$。
- 每个数字有两种选择,故递归的时间复杂度为 $O(2^n)$。
- 故总时间复杂度为 $O(m + 2^n)$。
空间复杂度
- 需要 $O(m + n)$ 的额外空间存储标记数组和递归的系统栈。
C++ 代码
const int N = 1010;
class Solution {
private:
int n, ans;
int seen[N];
void solve(int i, const vector<int> &nums, int k) {
if (i == n) {
ans++;
return;
}
solve(i + 1, nums, k);
if (seen[nums[i]] > 0)
return;
if (nums[i] + k < N) ++seen[nums[i] + k];
if (nums[i] - k > 0) ++seen[nums[i] - k];
solve(i + 1, nums, k);
if (nums[i] + k < N) --seen[nums[i] + k];
if (nums[i] - k > 0) --seen[nums[i] - k];
}
public:
int beautifulSubsets(vector<int>& nums, int k) {
memset(seen, 0, sizeof(seen));
n = nums.size();
ans = 0;
solve(0, nums, k);
return ans - 1;
}
};
同学是acwing的职员嘛,这更新速度太恐怖了
算法题解我只认wzc