100以内所有可以加为100的整数的组合

Question

import java.util.LinkedList;   
  
/**  
 * 100以内所有可以加为100的整数的组合。<br>  
 * 此处以10为例子。<br>  
 * 思路是，拿到第一个数，然后把后面的递归解析，<br>  
 * 原则后面的数不能小于当前这个数<br>  
 * 且不大于结果减去当前数.<br>  
 * <br>  
 * 比如 10,技术从0开始，则当前数为1，被递归解析数为9<br>  
 * 递归的起点为1，保证1不会再被解析。  
 *   
 * @author jayflee,老紫竹 java2000.net  
 *   
 */   
public class T {   
  public static void main(String[] args) {   
    split(10, 0);   
  }   
  
  static LinkedList<Integer> list = new LinkedList<Integer>();   
  
  public static void split(int n, int base) {   
    if (n == 0) {   
      System.out.println(list);   
      return;   
    }   
    for (int i = base + 1; i <= n; i++) {   
      list.addLast(i);   
      split(n - i, i);   
      list.removeLast();   //这行看不懂，为什么要删除最后一个元素？
    }   
  }   
  
}  

Answer 1

 list.removeLast();   //这行看不懂，为什么要删除最后一个元素？

Answer 2

递归算法中常见的问题.for (int i = base + 1; i <= n; i++) 
这个for循环的意思就是依次把i，放到List中，再进行一下次划分。
list.removeLast()就是把list.add(i)加进去的i，取走，下一次才能放进i+1去啊，否则，i还留着，逻辑不对了。

Answer 3

这个list就是起到一个输出的作用，没有参加运算，楼主再想想就明白了。呵呵~~~貌似楼主把问题想复杂了

Answer 4

请问，为什么要再拿走i,逻辑上是怎么不对的。
我想它的逻辑就是，先拿走1,让剩下的数找出99的组合，再拿走2,让下的数找97的组合，以此类推，直到找0的组合，这时前面拿出的数（存在list里）相加就是指定的数了。但我不明白为什么还要删掉每次放进去的。

Answer 5

因为每次都会产生一个新的n，那么它会把它首先加到list中去，接着再把这个n再一次的逐一化小，直到满足n == 0 返回，此时产生了一个新的结果。如果没有任意一个时候使得n == 0.那么显然没有找到结果，那就把先前加入的再逐一进行删除.
split(10, 0)
    for(int i = 1; i <= 10; i++) {
list.addLast(1);     --> add 1
split(9, 1);
list.addLast(2);     --> add 2
split(7, 2);    
list.addLast(3);    --> add 3
split(4,3);
list.addLast(4) --> add 4
split(0,4); 
 print(list> --> return; 产生结果1 : 1,2,3,4
removeLast() --> remove 4;
i++
list.addLast(5) --> add(5);
split(7,5);
list.addLast(6);  --> add 6;
split(1,6);  -->break;
removeLast()  --> remove 6;
i++;  --> break;
removeLast() --> remove 5;
i++;
split(7,6);
list.addLast(7); --> add 7;
split(0,7); --> break;
removeLast() --> remove 7;
i++ --> break;
split(7,7); --> break;
..........   -->  这中间还会产生新的结果
......
......
split(0,10) --> 返回结果 10
}

Answer 6

递归， 
list.removeLast();就是说要么不符合for循环，要么执行return语句返回来。

Answer 7

假设 求3//注意list是static的
循环以1开始的结果 add(1) （2，1）循环结束后-> remove(1) 由于递归且1不能再循环 去循环(2,1)
add(2) 循环（0,2）结束后-> remove(2)
由于递归优先先去循环(0,2),n=0返回 remove(2),再返回 再去remove(1)
结果list中是（1，2）其实主要原因是比如求5（注意加入进来和删除是成对的，如果能循环到0证明有结果 也就不会成对了）， 求出1，2，3 如果以1开始的还有其他（1，4）就求出 如果没有程序不会循环到0也就不会return 然后1就会被从list中去掉 开始循环2开始的 同样的道理

Answer 8

bigbug9002 哇。。得 红 了。。
恭喜。。

Answer 9

我把循环结构变成了顺序结构。把split(10,0)变成了split(4,0)
如果没有list.removeLast()程序逻辑是不是不对？

Answer 10

这个List用堆栈更形象一些。  public static void main(String[] args) {
    split(11, 0);
  }  static Stack<Integer> list = new Stack<Integer>();  public static void split(int n, int base) {
    if (n == 0) {
      System.out.println(list);
      return;
    }
    for (int i = base + 1; i <= n; i++) {
      list.push(i);
      split(n - i, i);
      list.pop();
    }
  }

Answer 11

http://blog.csdn.net/yanliang_xt/archive/2009/09/02/4512988.aspx
开始也觉得不好理解。然后画了下图思路就感觉清晰多了。。
为什么要list.remove() 因为你最近加的这个数不满足要求(也就是你加进去的这个数使得最终结果大于100了)，它是罪魁祸首，那你说还把它留在上面干嘛,所以就剔除它，再拿其它的数去试探。