python/C++专题课程/深度优先搜索/【递归入门】组合+判断素数.cpp

#include<iostream>
#include<cstring>
using namespace std;

bool isprime(int n) {
	if (n<=1)
		return false;
	for (int i=2; i*i<=n; i++)
		if (n%i==0)
			return false;

	return true;
}//判断素数

int a[22];
int b[22];
int p[22];
bool vis[22];
int n,k,sum,ans;

void dfs(int index) {
	if (index==k+1) {
		if (isprime(sum))
			ans++;//看是否加起来是素数
		for (int i=1; i<=index-1; i++)
			cout<<p[i]<<" ";
		cout<<endl;
		return ;
	}

	for (int i=1; i<=n; i++) {
		if (vis[i]==false  &&  i>p[index-1]) { //保证这个排列是按顺序来的，避免重复计算导致答案错误
			p[index] = i;
			vis[i] = true;
			sum+=a[i];//最巧妙的地方，，利用全排列的排列过程中，来加上我输入的数字
			dfs(index+1);
			vis[i] = false;
			sum-=a[i];//有加就有减
		}
	}
}


int main() {
	memset(b,0,sizeof(b));
	memset(vis,0,sizeof(vis));
	cin>>n>>k;
	for (int i=1; i<=n; i++)
		cin>>a[i],p[i]=i;//一开始要从第一个排列填好  才开始遍历 ，这与传统的dfs全排列做了点变化

	ans=0;

	dfs(1);
	cout<<ans<<endl;

	return 0;
}
//妈的，这个答案真巧妙