题目链接https://www.luogu.com.cn/problem/P1036
一道简单的dfs题,问题在于去重,怎么去重
最刚开始想的思路是 先排序,然后用标记的方式确保每组每个数字选一个,记录上一个数字,然后判断升序(想复杂了)
其实只要枚举的顺序是升序就保证了不重复数字
.....我是蒟蒻
上代码
#include<bits/stdc++.h> #define ll long long using namespace std; ll n,k; ll a[25]; ll sign[25]; ll ans=0; bool sushu(ll k) { ll i,m=sqrt(k); for(i=2;i<=m;i++) { if(k%i==0) return false; } return true; } void dfs(ll cur,ll sum,ll startx) { ll j; if(cur>=k) { if(sushu(sum)) { ans++; } return; } for(j=startx;j<=n;j++) { dfs(cur+1,sum+a[j],j+1); } return; } int main() { cin>>n>>k; ll i; for(i=1;i<=n;i++) cin>>a[i]; dfs(0,0,1); cout<<ans; }