在递归的时候用不用考虑这个数字 是选还是不选 ?
#include <bits/stdc++.h>
#include <map>
using namespace std;
// Finja_xh
// Allen_9
const int N = 1e8+5;
int data[N];
int n , k;
int ans = 0;
bool K[N];
//map<int , bool> F;
// cout <<
bool uni (int c)
{
for(int i = 2; i <= sqrt(c); i ++)
{
if(c % i == 0 )
return false;//合数,不符合要求
}
return true;
}
void dfs (int step,int sum,int x)
{
if(step > n) return ;
if(x > k) return ;
// cout << "step = " << step << " sum = " << sum << " x = " << x <<endl;
if(x == k)
{
// cout << "x = " << x << " k = "<< k <<endl;
if(K[sum] == 0)
{
if (uni(sum))
{
ans ++ ;
// cout << "sum = " << sum <<endl;
K[sum] = 1;
}
}
}
for(int i = step ; i <= n ; i++)
{
dfs(step + 1 , sum + data[step + 1], x + 1);
dfs(step + 1 , sum , x);
}
}
int main()
{
cin >> n >> k;
for (int i = 1; i <= n ; i++)
cin >> data[i];
dfs(0,0,0);
cout << ans;
return 0;
}