P1036 选数

组合型枚举，注意选满k个而不是n个即可回溯

const int N=25;
int a[N];
int n,k;
int ans;

bool check(int x)
{
    if(x < 2) return false;
    for(int i=2;i*i<=x;i++)
        if(x % i == 0)
            return false;
    return true;
}

void dfs(int u,int sum,int last)
{
    if(u == k)
    {
        if(check(sum)) ans++;
        return ;
    }

    for(int i=last;i<n;i++)
        dfs(u+1,sum+a[i],i+1);
}

int main()
{
    cin>>n>>k;

    for(int i=0;i<n;i++) cin>>a[i];

    dfs(0,0,0);

    cout<<ans<<endl;

    //system("pause");
}

P1036 选数

原文：https://www.cnblogs.com/fxh0707/p/13686948.html