解：
代碼：
#include<bits/stdc++.h>
using namespace std;
int ans=0;
int n,k,arr[25];
int Isprime(int n)
{
if(n<2) return 0;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
return 0;
}
return 1;
}
void f(int flag,int num,int sum)
{
if(num==0)
{
if(Isprime(sum))
{
ans++;
return;}
}
if(n-flag+1<num) return;//剪枝優化，下文有解釋
for(int i=flag;i<=n;i++)
{
f(i+1,num-1,sum+arr[i]);
}
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>arr[i];
}
f(1,k,0);
cout<<ans;
return 0;
}解析：
思路：我們現在要從n個數中選出k個（任意搭配），然後判斷他們的和是不是素數，我們使用遞歸枚舉的方法，枚舉每一種可能，最重要的就是遞歸函數
void f(int flag,int num,int sum)
{
if(num==0)
{
if(Isprime(sum))
{
ans++;
return;}
}
if(n-flag+1<num) return;
for(int i=flag;i<=n;i++)
{
f(i+1,num-1,sum+arr[i]);
}
}flag: 當前從哪個位置開始選擇（避免重複）num: 還需要選擇幾個數字sum: 當前已選數字的和- 由於本題數組下標我是從1開始定義的，所以最初調用函數時，函數是f（1，k，0）參數是1
- 舉例説明：如下
n=4, k=2
數組: [1, 2, 3, 4]
初始調用：f(1, 2, 0)
flag=1, num=2, sum=0
需要從位置1開始選2個數
第1層循環 i=1 to 4:
├─ i=1: f(2, 1, 0+1) // 選了1，還需要選1個
│ 第2層循環 i=2 to 4:
│ ├─ i=2: f(3, 0, 1+2) → 組合[1,2] sum=3 → 質數 ✓ ans=1
│ ├─ i=3: f(4, 0, 1+3) → 組合[1,3] sum=4 → 不是質數
│ └─ i=4: f(5, 0, 1+4) → 組合[1,4] sum=5 → 質數 ✓ ans=2
│
├─ i=2: f(3, 1, 0+2) // 選了2，還需要選1個
│ 第2層循環 i=3 to 4:
│ ├─ i=3: f(4, 0, 2+3) → 組合[2,3] sum=5 → 質數 ✓ ans=3
│ └─ i=4: f(5, 0, 2+4) → 組合[2,4] sum=6 → 不是質數
│
└─ i=3: f(4, 1, 0+3) // 選了3，還需要選1個
第2層循環 i=4 to 4:
└─ i=4: f(5, 0, 3+4) → 組合[3,4] sum=7 → 質數 ✓ ans=4for循環，第一輪for循環將i to n了一遍，第一個數從1到n都選了一遍
第二輪遞歸循環，在第一輪已經選中的第一個數的情況下，給參數加了1，就是f（i+1，....，...）這個，所以第二個數肯定是從第一個數的後面的位置繼續選取，把後面的數全部過一遍，
第三輪在前兩輪的基礎上繼續遞歸循環
剪枝優化：
if(n-flag+1<num)：意思是：剩餘元素數量 < 還需要選的元素數量時，直接返回
比如説現在選到倒數第二個元素（每輪循環都會遍歷一遍當前數後面的數），但是我還需要選擇三個數來相加，不符合就return
例如 1,2，3,4,5我現在要選三個數相加，第一個數我選了4，就只能再選一個5，就沒數能加了，直接return就好了，不必考慮後面了
本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。
