100，50，20，10元组合

今天去看了看算法 ，顺便说一下 那个德问论坛不错，那里的人挺牛逼。当然这里也很好。

说说这个题 可能有人听过把。就是100，50，20，10各有1，2，5，10张，进行组合，有多少是一百的。看论坛里他们写的代码实在是麻烦。这里给出我的解决方法。



import java.util.Stack;

public class Combination {

private static Stack<Integer> money=new Stack<Integer>();//栈
private static int[] sum={5,5,2,1}; //提供给予的10，20，50，100 对应的个数
private static int[] num={0,0,0,0}; //记录下 当前用过的次数。
private static int[] coin={10,20,50,100};//给予的钞票面值
private static int count=0; //记录总共的可能数


public static void main(String args[]){
Commoney(100);
System.out.println("总数是："+count);

}

public static void Commoney(int need){
for(int i=0;i<4;i++){
int dollar=coin[i];
//满足 1.100还没有分完。 2当前栈中没值，或者比前面的小，这样是为了有序。是结果集不重复。 3.当前的钞票个数还米有用完
if(need-dollar>=0&&(money.size()==0||dollar<=money.get(money.size()-1))&&num[i]<sum[i]){
money.push(dollar);
num[i]++;
if(need-dollar>0){
Commoney(need-dollar);
}
else{
count++;
  for (Integer m: money){  
       System.out.print (m);  
       System.out.print (" ");  
       }  
   System.out.println();  
}
money.pop();
num[i]--;
}
}
}

}