选数

题目链接：https://www.luogu.org/problemnew/show/P1036

题目描述

已知 n个整数以及1个整数k(k<n)。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4,k=3，4个整数分别为3,7,12,19时，可得全部的组合与它们的和为：
3+7+12=22
3+7+19=29
7+12+19=38
3+12+19=34
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3+7+19=293+7+19=29。

样例输入

4 3
3 7 12 19

样例输出

1

思路

    遍历数组，每一个数只有两种情况：选与不选，当选了k个数时，判断是否为素数，然后返回；

完整代码

#include<bits/stdc++.h>
using namespace std;
int n,k,a[22],ans;
int prime(int x) 
{
    for(int i=2;i*i<=x;i++)
        if(x%i==0)return 0;
    return 1;
}
void f(int x,int z,int t)//x为当前的数的下标  z为和  t为计数 
{
    if(t==k&&prime(z)){
        ans++;
        return;
    }
    if(x>=n)return;
    f(x+1,z,t);
    f(x+1,z+a[x+1],t+1);
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    f(1,0,0);
    f(1,a[1],1);
    cout<<ans;    
    return 0;
}