1666. 组合+判断素数(回顾)

1666. 组合+判断素数

中文English

给定 n 个整数和一个整数 k, 你可以从中选择 k 个整数, 现在，要求你计算出k个数和为素数共有多少种方案。

样例

样例 1:

输入：a=[3,7,12,19]，k=3
输出：1
解释：
There are 4 ways
3+7+12=22　　3+7+19＝29　　7+12+19＝38　　3+12+19＝34  
and only 29 is a prime.

样例 2:

输入：a=[1,2,3], k=2
输出：2
解释：
There are 3 ways
1 + 2 = 3         1 + 3 = 4      2 + 3 =5
and only 3 and 5 are primes.

注意事项

n 不超过 1010
k 不超过 n

class Solution:
    """
    @param a: the n numbers
    @param k: the number of integers you can choose
    @return: how many ways that the sum of the k integers is a prime number
    """
    def getWays(self, a, k):
        # Write your code here
        #首先找到所有的组合，for循环内嵌dfs，然后给出子函数，判断是否是素数
        
        results = []
        self.getAllArray(results, a, [], k)
        count = 0 
        
        #print(results)
        for result in results:
            if self.isPrime(result):
                count += 1 
        
        return count
        
    #递归的传参
    def getAllArray(self,results, a, array, k):
    
        #递归的出口
        if (k == 0):
            results.append(sum(array))
        
        #递归的拆解
        for i in range(len(a)):
            self.getAllArray(results, a[i + 1: ], array + [a[i]], k - 1)
        
    
    def isPrime(self, num):
        for i in range(2, num):
            if num % i == 0:
                return False
        
        return True