先看题目：
Prime Solutions
以下是一段中學時代的慘痛回憶…每當學到排列組合的單元時，最痛苦的不是分析題目，也不是帶錯公式或計算錯誤，而是所謂的「苦工題」，以下這題是個例子:
給定正整數N與S，求出方程式(1)的所有質數解(全為質數)。
遇到這題，通常只能硬著頭皮將每一組以「土法煉鋼」的方式一一列出，然而到了大學修過程式設計與演算法課，俾使我們能在電腦上撰寫程式輕鬆解決此問題。
INPUT
第一行一樣為測資個數
每一行輸入正整數與正整數，N與S之間相隔一個空白鍵。
(提示: 計算之前先考慮方程式有沒有解可以加速程式執行。)
OUTPUT
N個質數相加剛好等於S有哪些可能的組合，質數可以重複,但請由小到大排列，若無解(例如100個質數相加等於23無解)則輸出0，解可能不只一組，若有多組解時，靠左邊的數字較小的那組解則優先輸出，請參照SAMPLE OUTPUT。每一筆測資的輸出之間也換一行。
SAMPLE INPUT
4
2 5
100 23
3 8
4 25
SAMPLE OUTPUT
2 3
0
2 3 3
2 2 2 19
2 3 3 17
2 3 7 13
2 5 5 13
2 5 7 11
---------------分割线---------------
首先先来解释一下题目，首先input第一行的4是资料的笔数，之后的2 5代表 5以内的质数取2个相加等于5，5以内的质数有 2、3，2+3=5所以输出2 3。
本题主要考验的是质数的求解（简单）以及可重复排列数的实现（时间复杂度较大）
根据题目需要，可以大概得到这样一个流程：
关键的难点在于可重复排列数，其思路是设定一个标签来标记当前的位置，循环+递归。同时附加从大到小或者从小到大排列能够节省大量的运算时间。
下面来看代码：
1 /** 2 * @Title: getCombination 3 * @Description: 递归取得可重复排列数 4 * @throws 5 */ 6 private void getCombination(ArrayListarr, int n, int begin, ArrayList rs, int index) { 7 if (n == 0) { 8 rsList.add(rs); 9 return;10 }11 for (int i = 0; i < arr.size(); i++) {12 13 if (index == 0 || arr.get(i) >= rs.get(index - 1)) {14 rs.set(index, arr.get(i));15 getCombination(arr, n - 1, i + 1, clone(rs), index + 1);16 }17 }18 }
1 /** 2 * @Description: 得到质数表 3 */ 4 private ArrayListgetAllPrimeNum(int num) { 5 ArrayList primeNums = new ArrayList<>(); 6 for (int i = 2; i <= num; i++) { 7 if (isPrimeNumber(i)) 8 primeNums.add(i); 9 }10 return primeNums;11 }
1 /** 2 * @Title: isPrimeNumber 3 * @Description: 判断是否是质数 4 */ 5 public boolean isPrimeNumber(int number) { 6 if (number <= 1) 7 return false; 8 for (int i = 2; i <= Math.sqrt(number); i++) { 9 if (number % i == 0)10 return false;11 }12 return true;13 }
1 /** 2 * @Title: isEquals 3 * @Description: 判断arr所有数的和是否等于sum 4 */ 5 public boolean isEquals(ArrayListarr, int sum) { 6 int temp = 0; 7 for (int num : arr) { 8 temp += num; 9 }10 return sum == temp;11 }
1 /** 2 * @Title: sort 3 * @Description: 无聊的排序而已，按照hashCode排序 4 */ 5 public void sort(ArrayList> rs) { 6 for (int i = 0; i < rs.size(); i++) { 7 for (int j = i + 1; j < rs.size(); j++) { 8 if (rs.get(i).hashCode() > rs.get(j).hashCode()) { 9 ArrayList temp = rs.get(i);10 rs.set(i, rs.get(j));11 rs.set(j, temp);12 }13 }14 }15 }
1 /** 2 * @Title: primeSolution 3 * @Description: 程序主逻辑 4 */ 5 public ArrayList> primeSolution(int n, int num) { 6 ArrayList arr = getAllPrimeNum(num); 7 ArrayList temp = getAllPrimeNum(n); 8 ArrayList > okList = new ArrayList<>(); 9 10 while (temp.size() < n) {11 temp.add(0);12 }13 if ((!isHasResult(arr, num, n)) && n > arr.size())14 return null;15 16 getCombination(arr, n, 0, temp, 0);17 for (ArrayList rs : rsList) {18 if (isEquals(rs, num) && rs.size() == n) {19 okList.add(rs);20 }21 }22 return okList;23 }
完整代码如下：
1 import java.util.ArrayList; 2 import java.util.Scanner; 3 4 /** 5 * @author lcc 957109587@qq.com 6 * @version 2016年3月9日 下午9:00:43 7 * @Description 8 */ 9 public class PrimeSolutions { 10 static ArrayList > rsList = new ArrayList<>(); 11 12 public static void main(String[] args) { 13 @SuppressWarnings("resource") 14 Scanner scan = new Scanner(System.in); 15 ArrayList okList = new ArrayList<>(); 16 PrimeSolutions primeSolutions = new PrimeSolutions(); 17 int runtimes = scan.nextInt(); 18 for (int i = 0; i < runtimes; i++) { 19 int n = scan.nextInt(); 20 int num = scan.nextInt(); 21 okList.add(primeSolutions.primeSolution(n, num)); 22 } 23 for (int j = 0; j < okList.size(); j++) { 24 if (okList.get(j) == null) { 25 System.out.println(0); 26 } else { 27 primeSolutions.outPut(okList.get(j)); 28 } 29 if (j < okList.size() - 1) { 30 System.out.println(); 31 } 32 } 33 } 34 35 /** 36 * @Title: primeSolution 37 * @Description: 程序主逻辑 38 */ 39 public ArrayList > primeSolution(int n, int num) { 40 ArrayList arr = getAllPrimeNum(num); 41 ArrayList temp = getAllPrimeNum(n); 42 ArrayList > okList = new ArrayList<>(); 43 44 while (temp.size() < n) { 45 temp.add(0); 46 } 47 if ((!isHasResult(arr, num, n)) && n > arr.size()) 48 return null; 49 50 getCombination(arr, n, 0, temp, 0); 51 for (ArrayList rs : rsList) { 52 if (isEquals(rs, num) && rs.size() == n) { 53 okList.add(rs); 54 } 55 } 56 return okList; 57 } 58 59 /** 60 * @Title: getCombination 61 * @Description: 递归取得可重复排列数 62 * @throws 63 */ 64 private void getCombination(ArrayList arr, int n, int begin, ArrayList rs, int index) { 65 if (n == 0) { 66 rsList.add(rs); 67 return; 68 } 69 for (int i = 0; i < arr.size(); i++) { 70 71 if (index == 0 || arr.get(i) >= rs.get(index - 1)) { 72 rs.set(index, arr.get(i)); 73 getCombination(arr, n - 1, i + 1, clone(rs), index + 1); 74 } 75 } 76 } 77 78 /** 79 * @Title: clone 80 * @Description: 深拷贝List 81 */ 82 private ArrayList clone(ArrayList rs) { 83 ArrayList tocopy = new ArrayList<>(); 84 for (int num : rs) { 85 int temp = num; 86 tocopy.add(temp); 87 } 88 return tocopy; 89 } 90 91 /** 92 * @Title: isHasResult 93 * @Description: 判断是否有结果条件之一 94 */ 95 public boolean isHasResult(ArrayList arr, int num, int n) { 96 for (int temp : arr) { 97 if (temp * n == num) { 98 return true; 99 }100 }101 return false;102 }103 104 /** 105 * @Title: isEquals 106 * @Description: 判断arr所有数的和是否等于sum107 */108 public boolean isEquals(ArrayList arr, int sum) {109 int temp = 0;110 for (int num : arr) {111 temp += num;112 }113 return sum == temp;114 }115 116 /**117 * @Description: 得到质数表118 */119 private ArrayList getAllPrimeNum(int num) {120 ArrayList primeNums = new ArrayList<>();121 for (int i = 2; i <= num; i++) {122 if (isPrimeNumber(i))123 primeNums.add(i);124 }125 return primeNums;126 }127 128 /**129 * @Title: isPrimeNumber130 * @Description: 判断是否是质数131 */132 public boolean isPrimeNumber(int number) {133 if (number <= 1)134 return false;135 for (int i = 2; i <= Math.sqrt(number); i++) {136 if (number % i == 0)137 return false;138 }139 return true;140 }141 142 /**143 * @Title: sort144 * @Description: 无聊的排序而已，按照hashCode排序145 */146 public void sort(ArrayList > rs) {147 for (int i = 0; i < rs.size(); i++) {148 for (int j = i + 1; j < rs.size(); j++) {149 if (rs.get(i).hashCode() > rs.get(j).hashCode()) {150 ArrayList temp = rs.get(i);151 rs.set(i, rs.get(j));152 rs.set(j, temp);153 }154 }155 }156 }157 158 /**159 * @Description: 按照格式输出rs160 */161 public void outPut(ArrayList > rs) {162 sort(rs);163 for (int i = 0; i < rs.size(); i++) {164 for (int temp : rs.get(i))165 System.out.print(temp + " ");166 System.out.println();167 }168 }169 }
欢迎指正！