Medium

题目描述

给你一个由正整数组成的数组 nums 和一个正整数 k。

如果 nums 的子集中，任意两个整数的绝对差均不等于 k，则认为该子集是一个 美丽 子集。

返回数组 nums 中 非空 美丽子集的数目。

nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才不同。

示例 1：

输入：nums = [2,4,6], k = 2
输出：4
解释：美丽子集为：[2], [4], [6], [2, 6]。
可以证明在数组 [2,4,6] 中只有 4 个美丽子集。

示例 2：

输入：nums = [1], k = 1
输出：1
解释：美丽子集为：[1]。
可以证明在数组 [1] 中只有 1 个美丽子集。

提示：

  • 1 <= nums.length <= 18
  • 1 <= nums[i], k <= 1000

解题思路

这道题要求计算所有不包含绝对差为 k 的元素对的非空子集数量。

主要思路：

  1. 回溯法（推荐）：由于数组长度最大只有 18，可以使用回溯法枚举所有可能的子集。核心思想是对每个元素，我们有选择和不选择两种决策。为了确保美丽子集的条件，我们需要跟踪当前已选择的元素。

  2. 计数数组优化：按照题目提示，先对数组排序，然后使用计数数组 cnt 记录每个值的出现次数。在回溯过程中，如果 cnt[nums[i] - k] > 0，说明已经选择了与当前元素差值为 k 的元素，不能再选择当前元素。

  3. 状态压缩 DP：也可以用位运算表示子集状态，但由于需要检查绝对差条件，实现较复杂。

算法流程：

  • 对数组排序，便于处理
  • 使用回溯函数，对每个位置决定选择或不选择
  • 用哈希表记录当前子集中的元素及其出现次数
  • 检查当前元素是否与已选元素存在绝对差为 k 的冲突
  • 递归处理下一个位置，最后统计所有美丽子集的数量

回溯法时间复杂度为 O(2^n)，但由于有剪枝条件，实际运行效率较好。

代码实现

class Solution {
public:
    int beautifulSubsets(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        unordered_map<int, int> cnt;
        return backtrack(nums, k, 0, cnt) - 1; // 减去空集
    }
    
private:
    int backtrack(vector<int>& nums, int k, int idx, unordered_map<int, int>& cnt) {
        if (idx == nums.size()) {
            return 1; // 找到一个子集（包括空集）
        }
        
        // 不选择当前元素
        int result = backtrack(nums, k, idx + 1, cnt);
        
        // 尝试选择当前元素
        if (cnt[nums[idx] - k] == 0) {
            cnt[nums[idx]]++;
            result += backtrack(nums, k, idx + 1, cnt);
            cnt[nums[idx]]--;
        }
        
        return result;
    }
};

class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:
        nums.sort()
        
        def backtrack(idx, cnt):
            if idx == len(nums):
                return 1  # 找到一个子集（包括空集）
            
            # 不选择当前元素
            result = backtrack(idx + 1, cnt)
            
            # 尝试选择当前元素
            if cnt.get(nums[idx] - k, 0) == 0:
                cnt[nums[idx]] = cnt.get(nums[idx], 0) + 1
                result += backtrack(idx + 1, cnt)
                cnt[nums[idx]] -= 1
                if cnt[nums[idx]] == 0:
                    del cnt[nums[idx]]
            
            return result
        
        return backtrack(0, {}) - 1  # 减去空集

public class Solution {
    public int BeautifulSubsets(int[] nums, int k) {
        Array.Sort(nums);
        var cnt = new Dictionary<int, int>();
        return Backtrack(nums, k, 0, cnt) - 1; // 减去空集
    }
    
    private int Backtrack(int[] nums, int k, int idx, Dictionary<int, int> cnt) {
        if (idx == nums.Length) {
            return 1; // 找到一个子集（包括空集）
        }
        
        // 不选择当前元素
        int result = Backtrack(nums, k, idx + 1, cnt);
        
        // 尝试选择当前元素
        if (!cnt.ContainsKey(nums[idx] - k) || cnt[nums[idx] - k] == 0) {
            if (!cnt.ContainsKey(nums[idx])) {
                cnt[nums[idx]] = 0;
            }
            cnt[nums[idx]]++;
            result += Backtrack(nums, k, idx + 1, cnt);
            cnt[nums[idx]]--;
        }
        
        return result;
    }
}

var beautifulSubsets = function(nums, k) {
    let count = 0;
    
    function backtrack(index, subset) {
        if (index === nums.length) {
            if (subset.length > 0) count++;
            return;
        }
        
        // Don't include current number
        backtrack(index + 1, subset);
        
        // Check if we can include current number
        let canInclude = true;
        for (let num of subset) {
            if (Math.abs(nums[index] - num) === k) {
                canInclude = false;
                break;
            }
        }
        
        if (canInclude) {
            subset.push(nums[index]);
            backtrack(index + 1, subset);
            subset.pop();
        }
    }
    
    backtrack(0, []);
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(2^n)最坏情况下需要遍历所有 2^n 个子集，但由于剪枝条件，实际运行时间会更好
空间复杂度O(n)递归调用栈深度为 n，哈希表最多存储 n 个元素

相关题目