2597.美丽子集的数目

链接：2597.美丽子集的数目
难度：Medium
标签：数组、哈希表、数学、动态规划、回溯、组合数学、排序
简介：给你一个由正整数组成的数组 nums 和一个 正 整数 k 。如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个 美丽 子集。返回数组 nums 中 非空 且 美丽 的子集数目。

题解 1 - typescript

• 编辑时间：2023-03-19
• 执行用时：580ms
• 内存消耗：48MB
• 编程语言：typescript
• 解法介绍：dfs。

function beautifulSubsets(nums: number[], k: number): number {
        nums.sort((a, b) => a - b);
        let res = 0;
        const s = new Set();
        dfs(0);
        return res;
        function dfs(cur: number) {
          if (cur == nums.length) {
            if (s.size) res++;
            return;
          }
          dfs(cur + 1);
          const num = nums[cur];
          if (!s.has(num - k)) {
            s.add(num);
            dfs(cur + 1);
            s.delete(num);
          }
        }
      }

题解 2 - cpp

• 编辑时间：2023-03-19
• 执行用时：152ms
• 内存消耗：31.2MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
public:
    int beautifulSubsets(vector<int>& nums, int k) {
        int res = 0, s[3005] = {0}, cnt = 0;
        dfs(res, nums, k, s, cnt, 0);
        return res;
    }
    void dfs(int &res, vector<int> &nums, int k, int *s, int &cnt, int cur = 0) {
        if (cur == nums.size()) {
            if (cnt) res++;
            return;
        }
        dfs(res, nums, k, s, cnt, cur + 1);
        int num = nums[cur];
        if (!s[num + 1000 - k] && !s[num + 1000 + k]) {
            cnt++;
            s[num + 1000] = 1;
            dfs(res, nums, k, s, cnt, cur + 1);
            s[num + 1000] = 0;
            cnt--;
        }
    }
};

题解 3 - python

• 编辑时间：2023-03-19
• 执行用时：3856ms
• 内存消耗：16.2MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:
        s = [False] * 3005
        cnt = 0
        res = 0
        def dfs(cur: int):
            nonlocal cnt, res
            if cur == len(nums):
                if cnt:
                    res += 1
            else:
                dfs(cur + 1)
                num = nums[cur]
                if not s[num + 1000-k] and not s[num + 1000+k]:
                    cnt += 1
                    s[num+1000] = True
                    dfs(cur+1)
                    s[num+1000] = False
                    cnt -= 1
        dfs(0)
        return res

题解 4 - rust

• 编辑时间：2023-03-19
• 执行用时：60ms
• 内存消耗：2.1MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn beautiful_subsets(nums: Vec<i32>, k: i32) -> i32 {
        let mut s = [false; 3005];
        let mut cnt = 0;
        let mut res = 0;
        fn dfs(
            nums: &Vec<i32>,
            k: usize,
            s: &mut [bool; 3005],
            cnt: &mut usize,
            res: &mut i32,
            cur: usize,
        ) {
            if cur == nums.len() {
                if *cnt != 0 {
                    *res += 1;
                }
            } else {
                dfs(nums, k, s, cnt, res, cur + 1);
                let num = nums[cur] as usize;
                if !s[num + 1000 - k] && !s[num + 1000 + k] {
                    *cnt += 1;
                    s[num + 1000] = true;
                    dfs(nums, k, s, cnt, res, cur + 1);
                    s[num + 1000] = false;
                    *cnt -= 1;
                }
            }
        }
        dfs(&nums, k as usize, &mut s, &mut cnt, &mut res, 0);
        res
    }
}