Leetcode 2597. The Number of Beautiful Subsets

[Woodyiiiiiii]

原题地址：2597. The Number of Beautiful Subsets

参考资料：

• 两种方法：回溯/动态规划（Python/Java/C++/Go）

这道题一开始没有什么特别思路，卡在不知道如何利用绝对值差为k这一条件。再观察数组长度和元素大小，就知道要用DFS递归，可能要用上记忆化搜索或者状态压缩。首先试着用暴力递归写了一版。

注意：

• 递归回溯有两种写法，第一种是枚举型，我经常写的这种。另一种是选或不选类型。后者比前者写法较简单些。两者时间复杂度都是O(2^n)，因为n最大为20，所以最大也就是1024*1024在10^8以下，所以勉强能AC。
• 同时注意到空间复杂度，既然在1000以内就要好好利用，不要用Set，而是用固定空间数组，这样更能加快运行时间

class Solution {
    int k;
    int[] nums;
    int[] cnt;
    int ans = 0;

    public int beautifulSubsets(int[] nums, int k) {
        this.k = k;
        this.nums = nums;
        Arrays.sort(this.nums);
        cnt = new int[1001];
        for (int i = 0; i < nums.length; ++i) {
            ++cnt[nums[i]];
            dfs(i);
            --cnt[nums[i]];
        }
        return ans;
    }

    private void dfs(int i) {
        if (i == nums.length) {
            return;
        }
        ++ans;
        for (int j = i + 1; j < nums.length; ++j) {
            if (nums[j] - k >= 1 && cnt[nums[j] - k] != 0) {
                continue;
            }
            ++cnt[nums[j]];
            dfs(j);
            --cnt[nums[j]];
        }
    }
}

class Solution {
    int k;
    int[] nums;
    int[] cnt;
    int ans = 0;

    public int beautifulSubsets(int[] nums, int k) {
        this.k = k;
        this.nums = nums;
        Arrays.sort(this.nums);
        cnt = new int[1001];
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == nums.length) {
            return;
        }
        dfs(i + 1);
        if (nums[i] - k >= 1 && cnt[nums[i] - k] != 0) {
            return;
        }
        ++ans;
        ++cnt[nums[i]];
        dfs(i + 1);
        --cnt[nums[i]];
    }
}

这是暴力递归的常规写法，没想到直接过了。赛后看其他人的留言，发现C++/python这样写会TLE，所以这是钻了编译器的空子，侥幸过了：）

那么尝试优化。那就要利用好绝对值之差为k这一条件了。

首先看下能不能用记忆化搜索，或者说缓存。换句话说，要看下有没有重复计算的部分，貌似没头绪。

接着看下能不能用状态压缩/DP，有人写了类似的做法但超时了，可以有空看看。

最后根据[Python] House Robber, O(n) By lee215的做法，利用不想交集合相乘和HashMap计算。

首先看到k，可以想到利用%k进行分组，这样保证了每组相互间不会形成绝对值之差为k的subset，每组进行数量相乘就可以求出最终答案。接着，要计算组内能形成满足条件的subset，则利用了198. House Robber题型的思想，对组内数组排序后计算相邻差不为k的个数。

class Solution {
    public int beautifulSubsets(int[] nums, int k) {
        Map<Integer, TreeMap<Integer, Integer>> map = new HashMap<>();
        for (int num : nums) {
            int key = num % k;
            map.putIfAbsent(key, new TreeMap<>());
            map.get(key).put(num, map.get(key).getOrDefault(num, 0) + 1);
        }
        int res = 1;
        for (int key : map.keySet()) {
            int pre = -1, dp0 = 1, dp1 = 0;
            for (int num : map.get(key).keySet()) {
                int v = (int) (Math.pow(2, map.get(key).get(num)) - 1);
                if (num - pre == k) {
                    int t = dp1;
                    dp1 = (dp0 * v);
                    dp0 += t;
                } else {
                    int t = dp1;
                    dp1 = (dp0 + dp1) * v;
                    dp0 += t;
                }
                pre = num;
            }
            res *= (dp0 + dp1);
        }
        return res - 1;
    }
}

这种求subset个数类型的题目，最终利用集合相乘和Hash的方法，最近还有一道类似的题目：2572. Count the Number of Square-Free Subsets