请写出java代码，实现一下方法，计算对于数字100，共有多少种组合方法。
（假设组合时可以使用的数字包括100，50，20，10，5，2，1），比如如果M为1，共有1中组合方法，即1*1个；
如果M为2，则共有2种组合方式，2*1个 和1*2个；
求出返回组合方法的个数。
package org.son;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Random;
import java.util.Set;
public class Compoine {
public static void main(String[] args) {
int num = 10;
int[] arr = { 100, 50, 20, 10, 5, 2, 1 };
System.out.println(getCom(num,arr));
}
// 获得随机的数
public static int getRandom(int[]arr) {
Random random =new Random();
return arr[random.nextInt(arr.length)];
}
publicstatic int getCom(intnum, int[] arr) {
// 使用set进行数据的统计，去除重复的map
Setset = new HashSet();
// 此处主要是对于个数的统计
for (inti = 0; i < 1000000000;i++) {
int sum = 0;
// 获得一个新的map存放数据
Mapmap = new HashMap();
while (sum <num) {
int x = getRandom(arr);
sum += x;
Object count =map.get(x);
if (count ==null) {
map.put(x, 1);
}
if (count !=null) {
int y = (int) count;
map.put(x, ++y);
}
if (sum ==num) {
set.add(map);
}
}
}
System.out.println(set);
return set.size();
}
}
但是这种性能很低，有没有大神帮忙写个性能比较高的代码。
public class Mytest {
private static int count;
public static void main(String args[]) {
int max = 10;
int[] cents = { 100, 50, 20, 10, 5, 2, 1 };
collectMoney(cents, 0, max, 0);
System.out.println("总共有" + count + "种搭配方法！");
}
public static void collectMoney(int[] cents, int beginIndex, int max, int result) {
if (result >= max) {
if (result == max) {
count++;
}
return;
}
for (int i = beginIndex; i < cents.length; i++) {
int cent = cents[i];
collectMoney(cents, i, max, result + cent);
}
}
}
