題目描述

已知?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）。

第二行?n?個整數，分別為?x1?,x2?,?,xn?（1≤xi?≤5×106）。

輸出格式

輸出一個整數，表示種類數。

輸入輸出樣例

輸入 #1復制

4 3
3 7 12 19

輸出 #1復制

1

題目鏈接：P1036 [NOIP 2002 普及組] 選數 - 洛谷

學習鏈接：遞推與遞歸 + DFS | 手把手帶你畫出遞歸搜索樹_嗶哩嗶哩_bilibili

解題思路：?

1. ?給出n個數，選k個數作為一個組合，對組合中元素求和，和為素數就累計cnt++
2. 設置一個桶t[]，將未選過的數裝進去，容量為k?
3. 若桶t[]裝夠了k個數，對其中元素求和，并進行判斷是否為素數，若為素數就累計
4. 剪枝：可選元素個數(n-start+1)<空位置個數(k-x+1)

?代碼如下：

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[25];//可選元素數組
int t[25];//記錄組合結果
int visited[25];//標記元素是否已訪問
int cnt=0;//累計方案數//判斷是否是素數
bool isprime(int sum)
{if(sum<2)	return true;for(int i=2;i<=sum/i;i++)if(sum%i==0)return false;return true;
} void dfs(int x,int start)
{//剪枝：可選元素個數(n-start+1)<空位置個數(k-x+1)if(n-start+1<k-x+1)	return ;//若枚舉的個數已經足夠，得到一個組合if(x>k){//對組合元素求和int sum=0; for(int i=1;i<=k;i++)sum=sum+t[i];//判斷sum是否是素數if(isprime(sum))cnt++;return ;//不管sum是不是素數，都要結束搜素 } for(int i=start;i<=n;i++){//將i位置的元素裝入t[] t[x]=a[i];//保證枚舉t[]的下一個位置的元素是從a[]的下一個位置開始dfs(x+1,i+1);//騰出位置，搜素下一個組合 t[x]=0;}
} 
int main()
{cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];dfs(1,1);//第一個位置從第一個元素開始枚舉cout<<cnt<<endl; return 0;
}

希望能幫助到各位同志，祝天天開心，學業進步！