1-100中,
求:5个不同数的和小于100的不重复组合的个数.
求效率比较高的算法。

用for循环写，这样效率太差了，排除.1000时就体现出来，递归20来秒，for得200来秒!

来看解答，用递归。 maxNum代表从1-100 total是和。

在递推阶段，必须要有终止递归的情况。

public class Test {
public static void main(String[] args) {
System.out.println(combination(100, 5, 100));
}
/**
* @param total
* 总数
* @param num
* 数字个数
* @param maxNum
* 最大数字
* @return
*/
public static int combination(int total, int num, int maxNum) {
if (total <= 1) { //在递推阶段，必须要有终止递归的情况。
return 0;
}
if (num == 1) { //在递推阶段，必须要有终止递归的情况。
if (maxNum > total)
return total - 1;
else
return maxNum - 1;
} else {
int total1 = 0;
for (int i = 1; i < maxNum; i++) {
total1 += combination(total - i, num - 1, i);
}
return total1;
}
}

}

-----------------------------------------------------------

int num=0;
for(int a=1;a<=100;a++) {
for(int b=a+1;b<=100;b++) {
if(a+b>=100) {
break;
}
for(int c=b+1;c<=100;c++) {
if(a+b+c>=100) {
break;
}
for(int d=c+1;d<=100;d++) {
if(a+b+c+d>=100) {
break;
}
for(int e=d+1;e<=100;e++) {
if(a+b+c+d+e>=100) {
break;
}
num++;
}
}
}
}
}
System.out.println(num);

---------------------------------------------

int num=0;
for(int a=1;a<=18;a++) {
for(int b=a+1;b<100-a;b++) {
for(int c=b+1;c<100-a-b;c++) {
for(int d=c+1;d<100-a-b-c;d++) {
for(int e=d+1;e<100-a-b-c-d;e++) {
//System.out.printf("%d %d %d %d %d\n",a,b,c,d,e);
num++;
}
}
}
}
}
System.out.println(num);

用时 从 18毫秒 降到 16毫秒

----------------------------------------------------------------------------

public class Main {

/**
* @param args
* the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
int i = 0;
int a, b, c, d, e;
int[] tmp = new int[4];

for (a = 1; a < 18; a++) {
tmp[0] = (100 - a - 1 - (1 + 1) - (1 + 1 + 1)) / 4;

for (b = a + 1; b <= tmp[0]; b++) {
tmp[1] = (100 - a - b - 1 - (1 + 1)) / 3;

for (c = b + 1; c <= tmp[1]; c++) {
tmp[2] = (100 - a - b - c - 1) / 2;

for (d = c + 1; d <= tmp[2]; d++) {
tmp[3] = (100 - a - b - c - d);

for (e = d + 1; e <= tmp[3]; e++) {
if (a + b + c + d + e < 100) {
// System.out.println(a+" "+b+" "+c+" "+d+"
// "+e);
i++;
} else {
break;
}
}
}
}
}
}
System.out.println(i);
}

}