【leetcode】2597. 美丽子集的数目

题目描述

leetcode.cn/problems/…/description

数据范围

• $1 \leq num.length \leq 18$

• $1 \leq nums[i], k \leq 1000$

思路

解法一

• 时间: 2000ms

刚看到这道题被吓了一跳, 题目求可行的集合数, 顺理成章的, 我就想到组合数学上去了. 不过还好, 这里是力扣不是codeforces, 如果在cf上遇到这道题都不知道要被折磨成什么样...

就像上面说的那样, 我最开始的思路是组合数学, 判断可行的组合的数量. 但是, 往下继续看, 就发现了惊喜, 数组长度就只有$18$, 这意味着什么, 这意味着可以直接暴力啊.

既然题目要求可行的方案数, 直接大力枚举所有的方案, 看能枚举出来多少个就代表着能有多少个可行解.

使用回溯的思想, 每次递归进入下一层的时候直接使用一个哈希表存一下不能使用的数, 也就是$nums[i]+k$和$nums[i]-k$这两个数. 但是这里有个小细节, 不能使用bool值, 因为同一个数可能被禁用多次, 比如说$[1,2,3]$如果选择$[1,3]$的话$2$就被标记了两次, 如果想要在次还原$2$这个值的话反过来也需要撤销标记两次, 但是bool值只有TrueorFalse, 然后就会解禁不该被使用的值...

class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:
        n = len(nums)
        mp = {}
        ans = 0

        def dfs(u: int) -> None:
            nonlocal ans
            for i in range(u, n):
                if mp.get(nums[i], 0) == 0:
                    # 标记不能被使用
                    mp[nums[i] + k] = mp.get(nums[i] + k, 0) + 1
                    mp[nums[i] - k] = mp.get(nums[i] - k, 0) + 1
                    # 递归
                    dfs(i + 1)
                    # 撤销标记
                    mp[nums[i] + k] -= 1
                    mp[nums[i] - k] -= 1
                    # 统计结果
                    ans += 1

        dfs(0)
        return ans

rust:

impl Solution {
    pub fn beautiful_subsets(nums: Vec<i32>, k: i32) -> i32 {
        let mut ans: i32 = 0;
        let mut mp: std::collections::HashMap<i32, i32> =
            std::collections::HashMap::<i32, i32>::new();

        fn dfs(
            i: usize,
            nums: &[i32],
            mp: &mut std::collections::HashMap<i32, i32>,
            k: i32,
            ans: &mut i32,
        ) {
            for j in i..nums.len() {
                if mp.get(&nums[j]).unwrap_or(&0) == &0 {
                    *mp.entry(nums[j] + k).or_insert(0) += 1;
                    *mp.entry(nums[j] - k).or_insert(0) += 1;
                    dfs(j + 1, nums, mp, k, ans);
                    mp.entry(nums[j] + k).and_modify(|v| *v -= 1);
                    mp.entry(nums[j] - k).and_modify(|v| *v -= 1);
                    *ans += 1;
                }
            }
        }

        dfs(0, &nums, &mut mp, k, &mut ans);
        ans
    }
}

不会只有我们两个人用Rust写这道题吧...

方法二

好了, 偷懒时间结束, 下面才是标准解法(官方题解的写法).

leetcode.cn/problems/the-number-of-beautiful-subs…