题目描述:
已知n个整数x1,x2,...,xn,以及1个整数k(k<n)。从n个整数中任选k个整数相加,可分别得到一系列的和。例如,当n=4,k=3,4个整数分别为3,7,12,19时,可得全部的组合与它们的和为:
3 + 7 + 12 = 22
3 + 7 +19 = 29
7 + 12 + 19 = 38
3 + 12 + 19 = 34
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数: 3 + 7 + 19 = 29。
输入格式
键盘输入,格式为:
n,k(1 <= n <= 20, k < n)
x1,x2,...,xn(1 <= xi <= 5000000)
输出格式
屏幕输出,格式为:1个整数(满足条件的种数)。
=====================分割线=============================================
从n个数中选择k个数去相加并判断和是否为素数,难点在于,如何知道后面选择的组合,和前面选择的组合是不是重复的,只是顺序不同罢了。如果用一个标记数组的话,操作起来太过复杂,要不断的标记和擦除。我们可以假设,这k个数中,只能从前往后选择,即当我们选择了一个下标为idx的元素时,如果当前选择元素的个数仍然小于k,那么我们只能往下标为idx+m(m>=1)的元素中继续选择,这样就可以避免了重复选择的问题了。
实现代码:
#include <iostream> int n, k; int res; int nums[25]; void DFS(int counts, int sum, int curIndex); bool isPrimer(int m); using namespace std; int main() { cin >> n >> k; for(int i = 0; i < n; i++){ cin >> nums[i]; } res = 0; DFS(0, 0, 0); cout << res << endl; return 0; } void DFS(int counts, int sum, int curIndex){ if(counts >= k){ if(isPrimer(sum)) res++; return; } for(int i = curIndex; i < n; i++) DFS(counts+1, sum+nums[i], i+1); return; } bool isPrimer(int m){ for(int i = 2; i*i <= m; i++){ if(m % i == 0) return false; } return true; }