題目描述

傳送門：https://www.luogu.com.cn/problem/P1036
已知n個整數x1,x2…xn,以及一個整數k(k<n)。從n個數字中任選k個數字相加，可分別得到一系列的和。例如當n=4，k=3，4個整數分別為3，7，12，9時，可得全部組合和它們的和為：
3+7+12=22

3+7+19=293+7+19=29

7+12+19=387+12+19=38

3+12+19=343+12+19=34。

現在，要求你計算出和為素數共有多少種。

例如上例，只有一種的和為素數：3+7+19=293+7+19=29。

輸入格式

鍵盤輸入，格式為：
n,k（1<=n<=20,k<n)
x1,x2…xn(1<=xi<=5000000)

輸出格式

屏幕輸出，格式為： 1個整數（滿足條件的種數）。

輸入樣例

4 3 3 7 12 19

輸出樣例

1

這里采用深度優先搜索，但是選數的難點在于遞歸中怎樣選擇不重復的k個數字，我們可以采用單調不降原則。
例如，我們從6個數字1 2 3 4 5 6中選擇三個數字，怎樣選擇？
1 2 3
1 2 4
1 2 5
1 2 6
這是第一輪的枚舉
那么下一輪的枚舉，我們將第二個數字加1：
1 3 4
1 3 5
1 3 6
當第一個數字變為2時，
2 3 4
2 3 5
2 3 6
2 4 5
2 4 6
2 5 6
依此類推…
其他枚舉可能
3 4 5
3 4 6
3 5 6
4 5 6
重復上述過程，第一個數字一次變為 2 3 4 5 6即可。
這樣可以避免重復的選取，那體現在輸入的數字上，我們可以依靠索引，逐步選取當前選擇索引之后的元素，即可避免重復。

程序實現：

#include<bits/stdc++.h> using namespace std;int n, k; int a[25]; int ans = 0; bool isprime(int num)//素數判斷 不用多說 {for (int i = 2; i <= sqrt(num); i++)if (num % i == 0)return false;return true; }void dfs(int m, int sum, int start) {if (m == k){if (isprime(sum)) {ans++;return;//如果滿足選取了k個數組 且滿足素數要求 直接累加 返回}}for (int i = start; i < n; i++)//選取個數加以 sum累加 索引加一dfs(m + 1, sum + a[i], i + 1);//從當前索引依次遞歸后續元素//即加入選取了1 那么之后的遞歸選取為 a[1]a[2],a[1]a[3],a[1]a[4]...... } int main() {cin >> n >> k;for (int i = 0; i < n; i++)cin >> a[i];dfs(0, 0, 0);//初始狀態深搜cout << ans << endl; }

算法參考：https://www.luogu.com.cn/user/120868

總結

以上是生活随笔為你收集整理的【洛谷】选数---深度优先搜索+单调不降去重的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。