楼主:
yam276 ('_')
2024-05-23 15:37:59※ 引述《Rushia (早瀬ユウカの体操服 )》之铭言：
: https://leetcode.com/problems/the-number-of-beautiful-subsets/description
: 2597. The Number of Beautiful Subsets
: 给你一个阵列表示一个集合和一个数字k，求出美丽子集数量，美丽子集是一个非空子集合
: ，所有子集元素彼此相差绝对值不会等于k。
:
: 思路：
: 1.回溯法，每次把元素加到当前子集前先检查是否包含+k或-k，没有才加。
中间的部分是用别人的方法
我本来的code一直卡在其中一个Test Case
这辈子就这样了
Code:
impl Solution {
pub fn beautiful_subsets(mut nums: Vec<i32>, k: i32) -> i32 {
nums.sort_unstable();
let n = nums.len();
fn solve(nums: &Vec<i32>, k: i32, i: usize, subset: u32) -> i32 {
if i == nums.len() {
return 1;
}
let mut ans = 0;
let mut skip = false;
for j in 0..i {
if (subset & (1 << j)) != 0 {
if (nums[i] - nums[j]).abs() as i32 == k {
skip = true;
break;
}
}
}
if !skip {
ans += solve(nums, k, i + 1, subset | (1 << i));
}
ans += solve(nums, k, i + 1, subset);
ans
}
solve(&nums, k, 0, 0) - 1
}
}