19699_소-난다!

사용 알고리즘: 백트래킹

사용 언어: java

 

package week21;

import java.io.*;
import java.util.*;

public class Main {
	static int[] h;
	static int n, m;
	static List<Integer> primes = new ArrayList<>();
	static boolean[] notPrime = new boolean[9000];

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		//프라임이니
//		prime[2] = true;
//		prime[3] = true;
//		prime[5] = true;
//		prime[7] = true;
		for(int i=2; i<9000; i++) {
			if(!notPrime[i]) {
				for(int j=2; j*i<9000; j++) {
					notPrime[j*i] = true;
				}
			}
		}
		
		n = sc.nextInt(); // 소들의 수
		m = sc.nextInt(); //선별할 수
		h = new int[n]; //소들의 몸무게
		
		for(int i=0; i<n; i++) {
			h[i] = sc.nextInt();
		}
		
		back(0, 0, 0);
		
		Collections.sort(primes);
		if(primes.size() == 0) System.out.println(-1);
		else {for(int i : primes) {
			System.out.print(i+" ");
		}}
	}
	
	private static void back(int idx, int cnt, int sum) {
		if(m == cnt) {
			if(!notPrime[sum] && !primes.contains(sum))
				primes.add(sum);
			return;
		}
		
		for(int i=idx; i<n; i++) {
			
			back(i+1, 1+cnt, sum+h[i]);
		}
	}

}