不明白这和深搜有什么关系。

思路

本题可以使用限制数量的子集枚举来解决。在 $1\le n\le20$ 的数据范围下，$O(2^n)$ 的时间复杂度可以通过。

AC Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=25;
ll n,k,a[N],ans;
int main(){
    scanf("%lld%lld",&n,&k);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(ll i=0;i<=(1<<n);i++)
        if(__builtin_popcount(i)==k){ // 限制数量为k
            ll cnt=0;
            for(ll j=0;j<n;j++)
                if(i&(1<<j))
                    cnt+=a[j+1];
            bool flag=1;
            for(ll i=2;i*i<=cnt;i++)
                if(cnt%i==0){
                    flag=0;
                    break;
                }
            if(flag)
                ans++;
        }
    printf("%lld",ans);
    return 0;
}