总结
1.搜索其实就是全部遍历一遍,只不过可以把遍历过的,以及接下来一看就知道不用遍历的不去遍历,也就是剪枝
2.一定要明确自己所设的搜索函数各个变量的含义!!
代码
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[30]={0};
int zs(int x)
{
for(int i=2;i*i<=x;i++)if(x%i==0)return 0;
return 1;
}
int ss(int len,int now,int sum)//代表以now为头节点的数组,已经取了len个值,取值和为sum时有多少种组合
{
if(n-now+1<k-len)return 0;//用不着搜索
if(len==k)
{
if(zs(sum))return 1;
else return 0;
}
return ss(len,now+1,sum)+ss(len+1,now+1,sum+a[now]);//穷举,对于存在的某种组合顺序来说,一个数不是用就是不用
// 能不能记忆轮到当前数时取了多少个数的状态?答案是不能,因为就算len相同now相同,sum不一定相同。这道题里就算记忆sum,内存也太大太浪费了
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
cout<<ss(0,1,0);
return 0;
}