6352.美丽子集的数目-337()

美丽子集的数目

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

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

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

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

示例 1：

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

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

提示：

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

解题思路1：dfs

由于数据量并不是十分大，可以使用dfs遍历所有的子集并判断是否符合题目给定的条件，在判断是否符合条件时我使用的是遍历的方法，进一步的优化可以使用哈希表或者是数组在O(1)的时间内判断是否存在nums[i] + k或者是nums[i] – k;至于dfs的写法，主要还是要画或者是imagine一棵递归树出来这样就可以对着递归树较好地写dfs了，时间复杂度为\(O(2^n)\).

code

class Solution {
public:
    //通过组合找到所有子集
    //判断子集是否美丽
    //提前终止dfs
    int ans = 0;
    void dfs(vector<int> & nums,vector<int> & path,int depth,int & k)
    {
        if(depth == nums.size()) return;
        
        for(int i = depth;i < nums.size();i ++)
        {
            bool flag = true;
            for(int j = 0;j < path.size();j ++)
            {
                if(nums[i] - path[j] == k) flag = false;
            }
            if(flag)
            {
                path.push_back(nums[i]);
                ans ++;
                dfs(nums,path,i + 1,k);
                path.pop_back();
            }
        }
        
    }
    int beautifulSubsets(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        vector<int> path;
        dfs(nums,path,0,k);
        return ans;
    }
};
————————

美丽子集的数目

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

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

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

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

示例 1：

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

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

提示：

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

解题思路1：dfs

由于数据量并不是十分大，可以使用dfs遍历所有的子集并判断是否符合题目给定的条件，在判断是否符合条件时我使用的是遍历的方法，进一步的优化可以使用哈希表或者是数组在O(1)的时间内判断是否存在nums[i] + k或者是nums[i] – k;至于dfs的写法，主要还是要画或者是imagine一棵递归树出来这样就可以对着递归树较好地写dfs了，时间复杂度为\(O(2^n)\).

code

class Solution {
public:
    //通过组合找到所有子集
    //判断子集是否美丽
    //提前终止dfs
    int ans = 0;
    void dfs(vector<int> & nums,vector<int> & path,int depth,int & k)
    {
        if(depth == nums.size()) return;
        
        for(int i = depth;i < nums.size();i ++)
        {
            bool flag = true;
            for(int j = 0;j < path.size();j ++)
            {
                if(nums[i] - path[j] == k) flag = false;
            }
            if(flag)
            {
                path.push_back(nums[i]);
                ans ++;
                dfs(nums,path,i + 1,k);
                path.pop_back();
            }
        }
        
    }
    int beautifulSubsets(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        vector<int> path;
        dfs(nums,path,0,k);
        return ans;
    }
};