题解 | #[NOIP2002]选数#

解决此题的关键在于如何使用“排列组合”。我们要从N中取M个数，后进行相加，其次再判断是否为素数。我们先用n接收所有的数的个数，用k来接收需要选取的个数。其实我们构造函数dp（）,并传入三个参数，依次为num,sum,i，当num==k时，证明完成了一组（三个数之和），接下里我们来判断是否为素数，这里我们用一个方法来判断，其实不用方法也行，根据自己的需求能解出题目即可，即可完成此题

import java.util.Scanner;
public class Main {

static int n, k, ans, a[];
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    k = sc.nextInt();
    a = new int[n];
    for(int i = 0; i < n; i++) {
        a[i] = sc.nextInt();
    }
    dp(0, 0, 0);
    System.out.println(ans);
}
public static boolean isPrime(int x) {
    for(int i = 2; i * i < x; i++) {
        if(x % i == 0) {
            return false;
        }
    }
    return true;
}
public static void dp(int num, int sum, int i) {
    if(num != k) {
        for(; i < n; i++) {
            dp(num + 1 , sum + a[i], i + 1);
        }
    }
    else {
    	if(isPrime(sum)) {
    		ans++;
    	}
    }
}

}