选数 计蒜客 T2116 解释如何取得唯一解

选数 - 计蒜客 T2116 - Virtual Judge (vjudge.net)

[NOIP2002]选数 - 题库 - 计蒜客 (jisuanke.com)

这题素数判断之类的其他博客都写过了

我主要尝试解释如何保证数据不出现重复解

如题目所说，每个数据不能重复选择

这样的话，我们定义一个布尔数组来标记是否被选择过

3+7+19=29，它交换一下位置相加也是29

而样例的答案为1，所以不能出现重复解

那么可以再加个数组，表示结果是否出现过行吗？

不行，因为同一个结果可能出现多个解

似乎很难办，回过头来想想

第一次出现的解便是唯一正解，之后解的不同顺序一定是用到了之前的数

如 3 7 19， 当以 7 开头时， 只有用到之前的 3 ，才能出现重复解 7 3 19

所以我们保证用不到之前的数即可

自然也不会出现重复选取同一个数的问题

#include 
#include 
using namespace std;
const int N = 21;
int num[N];
int n, k;
int res;

bool isprime(int x)
{
	for (int i = 2; i <= sqrt(x * 1.0); i++)
	{
		if (x % i == 0) return false;

	}
	return true;
}

void dfs(int u, int sum, int i)
{
	if (u == k)
	{
		if (isprime(sum)) res++;
		return;
	}

	for (i ; i < n; i++)
	{
			dfs(u + 1, sum + num[i], i + 1);
	}
}


int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> num[i];
	dfs(0,0,0);
	cout << res << endl;
	return 0;
}