试题请参见: https://vijos.org/p/1128
题目概述
已知 n 个整数 x1,x2,…,xn, 以及一个整数 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个数. 得到k个数后求和, 并判断是否为素数.
遇到的问题
解题过程中主要遇到两个问题:
原题中叙述求素数共有多少种, 于是我使用set去重. 然后妥妥的WA了.在递归时, 需要指定当前搜索开始的下标(代码中的searchIndex), 否则结果会重复.源代码#include <iostream>#include <cmath>const int MAX_N = 20;int getSum(long long*, int, int);, int&);bool isPrime(long long);bool isAppeared(long long);int main() {int n = 0, k = 0;long long numbers[MAX_N] = {0};std::cin >> n >> k;for ( int i = 0; i < n; ++ i ) {std::cin >> numbers[i];}std::cout << getSum(numbers, n, k) << std::endl;return 0;}/** * 获取不同的素数结果的个数. * @param numbers n个数序列的集合 * @param n序列的长度 * @param k选取数的个数 * @return 不同的素数结果的个数 */int getSum(long long* numbers, int n, int k) {int totalResults = 0;bool isUsed[MAX_N] = {0};getSum(numbers, isUsed, n, k, 0, 0, 0, totalResults);return totalResults;}/** * 回溯: 获取n个数中选择k个值的总和. * @param numbersn个数序列的集合 * @param isUsedn个数的选择情况(第i个数是否被选中) * @param n序列的长度 * @param k选取数的个数 * @param searchIndex下次搜索的下标 * @param selectedNumbers 当前选择的个数 * @param sum当前的总和 * @param totalResults 当前不重复的和的个数 */sum, int& totalResults) {if ( selectedNumbers == k ) {if ( isPrime(sum) ) {++ totalResults;}}for ( int i = searchIndex; i < n; ++ i ) {if ( !isUsed[i] ) {isUsed[i] = true;getSum(numbers, isUsed, n, k, i, selectedNumbers + 1, sum + numbers[i], totalResults);isUsed[i] = false;}}}/** * 判断一个数是否为素数. * @param x 待判断的值 * @return 该数值是否为素数 */bool isPrime(long long x) {if ( x <= 2 ) {return false;}for ( int i = 2; i <= std::sqrt(x); ++ i ) {if ( x % i == 0 ) {return false;}}return true;}
，都成为命途中美丽的点缀，看天，看雪，安安静静，不言不语都是好风景。
