题目链接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;
 }