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(); //这行看不懂,为什么要删除最后一个元素?
}
}
}
/**
* 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(); //这行看不懂,为什么要删除最后一个元素?
}
}
}
这个for循环的意思就是依次把i,放到List中,再进行一下次划分。
list.removeLast()就是把list.add(i)加进去的i,取走,下一次才能放进i+1去啊,否则,i还留着,逻辑不对了。
我想它的逻辑就是,先拿走1,让剩下的数找出99的组合,再拿走2,让下的数找97的组合,以此类推,直到找0的组合,这时前面拿出的数(存在list里)相加就是指定的数了。但我不明白为什么还要删掉每次放进去的。
因为每次都会产生一个新的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
}
list.removeLast();就是说要么不符合for循环,要么执行return语句返回来。
循环以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开始的 同样的道理
恭喜。。
如果没有list.removeLast()程序逻辑是不是不对?
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();
}
}
开始也觉得不好理解。然后画了下图思路就感觉清晰多了。。
为什么要list.remove() 因为你最近加的这个数不满足要求(也就是你加进去的这个数使得最终结果大于100了),它是罪魁祸首,那你说还把它留在上面干嘛,所以就剔除它,再拿其它的数去试探。