P1036 选数

点击查看代码

#include<bits/stdc++.h>
using namespace std;int n,m;
int a[25];
long long ans;bool prime(int x)
{if(x==1||x!=2&&x%2==0) return false;for(int i=3;i<=x/i;i++) if(x%i==0) return false;return true;
}
//k表示当前已经选的数的个数，s表示当前的和，x表示下一个选择的数字
void dfs(int k,int s,int x)
{if(k==m){if(prime(s)) ans++;return;}//这样就相当于实现了从n个数中选m个数的功能，for循环结束返回，或者到达个数开始返回，并且因为是传值，所以不需要恢复for(int i=x;i<n;i++) dfs(k+1,s+a[i],i+1);
}int main()
{cin>>n>>m;for(int i=0;i<n;i++) cin>>a[i];dfs(0,0,0);cout<<ans<<endl;return 0;
}

核心在于实现了从n个数中选m的功能，for+递归，而且因为是传值所以不用恢复，很精简的实现