目录

1. 题目描述

2. 解题分析

2.1 暴力破解

2.2 优化解法

3. 代码实验

1. 题目描述

        给你一个整数数组 nums 。如果 nums 的一个子集中，所有元素的乘积可以表示为一个或多个 互不相同的质数 的乘积，那么我们称它为 好子集 。

        比方说，如果 nums = [1, 2, 3, 4] ：

• [2, 3] ，[1, 2, 3] 和 [1, 3] 是 好 子集，乘积分别为 6 = 2*3 ，6 = 2*3 和 3 = 3 。
• [1, 4] 和 [4] 不是 好 子集，因为乘积分别为 4 = 2*2 和 4 = 2*2 。

        请你返回 nums 中不同的 好 子集的数目对 取余（这个条件是个什么鬼？） 的结果。

        nums 中的 子集 是通过删除 nums 中一些（可能一个都不删除，也可能全部都删除）元素后剩余元素组成的数组。如果两个子集删除的下标不同，那么它们被视为不同的子集。

示例 1：
输入：nums = [1,2,3,4]
输出：6
解释：好子集为：

• - [1,2]：乘积为 2 ，可以表示为质数 2 的乘积。
• - [1,2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
• - [1,3]：乘积为 3 ，可以表示为质数 3 的乘积。
• - [2]：乘积为 2 ，可以表示为质数 2 的乘积。
• - [2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
• - [3]：乘积为 3 ，可以表示为质数 3 的乘积。

示例 2：
输入：nums = [4,2,3,15]
输出：5
解释：好子集为：

• - [2]：乘积为 2 ，可以表示为质数 2 的乘积。
• - [2,3]：乘积为 6 ，可以表示为互不相同质数 2 和 3 的乘积。
• - [2,15]：乘积为 30 ，可以表示为互不相同质数 2，3 和 5 的乘积。
• - [3]：乘积为 3 ，可以表示为质数 3 的乘积。
• - [15]：乘积为 15 ，可以表示为互不相同质数 3 和 5 的乘积。

 
提示：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 30

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/the-number-of-good-subsets

2. 解题分析

2.1 暴力破解

        一个包含n个元素的集合的子集的集合构成所谓的幂集（power set），幂集的大小为，即包含n个元素的集合总共有个子集， 其中包含空集和它自身。空集不满足本题条件，可以不予考虑。暴力破解方法就是对这个子集进行遍历，对每个子集的乘积进行质因数分解，看看质因数分解是不是只包含不同的质数。

        此外，1不算是质数，而且乘以1也不会导致乘积变化，因此如果集合中包含1的话，可以把1先撇开不考虑，对除1以外的子集进行求解。然后所求得解集中每个子集再加上1这个元素构成的子集同样满足原题条件。

        显而易见的是，暴力破解中会导致大量的重复的运算。如何避免这些重复运算呢？

2.2 优化解法

        显然，如果一个数的质因数分解包含重复的质因子，比如说平方数4或者18=2*3*3等，包含它的子集肯定无法满足条件。所以，这一类是可以排除掉的。

        题中没有明确说是否存在重复元素，但是显而易见的是存在重复元素对解集没有影响。当然为了保险起见可以先进行去重预处理。

        首先，去重预处理。

        其次，对各元素分别进行质因数分解，顺便排除1和包含平方数为因子的数。但是1的存在必须记忆，用于最后的结果生成

        第三，对子集进行遍历，将每个子集中各元素的质因数分解结果求并集，如果其中不存在重复元素则为一个合法解

        第四，如果原集合存在1的话，则将上一步所求解集进行扩充得到最终解

3. 代码实验

class Solution:

    def isPrime(self, x):
        for i in range(2,int(sqrt(x))+1):
            if x%i==0:
                return False
        return True

    def primeFactorization(self, n):
        ans = []
        
        i = 2        
        while n>=2:
            if self.isPrime(i):
                while n%i == 0:
                    n = n // i
                    ans.append(i)
            i = i + 1
        return ans
    
    def numberOfGoodSubsets(self, nums: List[int]) -> int:
        # 1. Repetition removal
        num_set = set(nums)
        # 2. Prime factorization for each element and record the existence of 1
        #    Remove the number with repetitive primes in the factorization
        #    Store the result in a dictionary
        primeFactor = dict()
        one_flag = False
        num_set_reduced = num_set.copy()
        ans = []
        for n in num_set:
            if n != 1:
                tmp = self.primeFactorization(n)
                if len(set(tmp)) == len(tmp):
                    primeFactor[n] = tmp
                else:
                    num_set_reduced.discard(n)
            else:
                num_set_reduced.discard(1)
                one_flag = True
        
        # 3. Traverse the power set                
        for k in range(1, len(num_set_reduced)+1):
            for subset in it.combinations(num_set_reduced,k):                
                primeSet = []
                for e in subset:
                    primeSet = primeSet + primeFactor[e]
                print(subset, primeSet)
                if len(set(primeSet)) == len(primeSet):
                    ans.append(list(subset))                
        # 4. If there is 1 in the original set
        if one_flag: # No need of give the list of the good subset, only the numbers!
            # ans1 = []
            # for each in ans:
            #     print(each)
            #     ans1.append(each + [1])
            # ans = ans + ans1             
            return 2 * len(ans)
        else:
            return len(ans)

if __name__ == '__main__':        
    
    sln = Solution()
    # print(sln.isPrime(17))
    # print(sln.primeFactorization(105))
    
    nums = [1,2,3,4]
    print('nums={0}:  {1}'.format(nums,sln.numberOfGoodSubsets(nums)))
    print()
    
    nums = [4,2,3,15]
    print('nums={0}:  {1}'.format(nums,sln.numberOfGoodSubsets(nums)))
    print()
    
    nums = [6,8,1,8,6,5,6,11,17]
    print('nums={0}:  {1}'.format(nums,sln.numberOfGoodSubsets(nums)))
    print()   

很遗憾，提交后报告针对testcase：[6,8,1,8,6,5,6,11,17]结果错误。运行结果为30，反馈的结果为62。

不是很服气。。。针对[6,8,1,8,6,5,6,11,17]我直接手动枚举只能数出30个（{5,6,11,17}只有15个非空子集，全部满足，再乘以2就是30个）来。所以，题意理解有误？

偷看了下官解。利用了“1 <= nums[i] <= 30”的条件（完全没有注意到这个条件^-^汗ing），可以先把这个范围内的质数先枚举出来。。。呃。。。改日再战。不过以上解法即便正确，运行时间确实不是很乐观。。。需要优化。

回到本笔记系列总目录：

笨牛慢耕的Leetcode解题笔记(动态更新。。。)https://chenxiaoyuan.blog.csdn.net/article/details/123040889