面试题如下：把一个数组里的数组合全部列出，比如1和2列出来为1，2,12,21。
(面试题出自《Java程序员面试宝典》)
代码如下：
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;/**
* 把一个数组里的数组集合全部列出，比如1和2列出来为1，2,12,21
*/
public class ListAll {
public static void main(String[] args) {
String[] array = new String[] { "1", "2", "3" };
listAll(Arrays.asList(array), "");
}
/**
* 使用递归方法
* @param candidate 递归遍历的List集合
* @param prefix打印出的前缀
*/
public static void listAll(List<String> candidate, String prefix) {
System.out.println(prefix);
for (int i = 0; i < candidate.size(); i++) {
List temp = new LinkedList(candidate);// 转换为LinkedList便于安插和移动
listAll(temp, prefix + temp.remove(i));
}
}
}
输出结果为：
1
12
123
13
132
2
21
213
23
231
3
31
312
32
321
为了便于理解，在循环中加一句 System.out.println(“candidate is: ” + candidate);
public static void listAll(List<String> candidate, String prefix) {
System.out.println(prefix);
for (int i = 0; i < candidate.size(); i++) {
System.out.println("candidate is: " + candidate); // 此行代码便于理解递归
List temp = new LinkedList(candidate);// 转换为LinkedList便于安插和移动
listAll(temp, prefix + temp.remove(i));
}
}
这样输出结果为：
candidate is: [1, 2, 3]
1
candidate is: [2, 3]
12
candidate is: [3]
123
candidate is: [2, 3]
13
candidate is: [2]
132
candidate is: [1, 2, 3]
2
candidate is: [1, 3]
21
candidate is: [3]
213
candidate is: [1, 3]
23
candidate is: [1]
231
candidate is: [1, 2, 3]
3
candidate is: [1, 2]
31
candidate is: [2]
312
candidate is: [1, 2]
32
candidate is: [1]
321
算法其实就是现在有几个数，就先分成几组，例如[1,2,3]那么递归第一层就是1-[2,3],2-[1,3],3-[1,2]。然后把list传入继续递归以1-[2,3]为例：又分为2-[3], 3-[2],并且把这些与第一层的1拼接成为12-[3], 13-[2],然后list继续递归下去，这样就把1开头的组合都排列完了。2,3开头的都是同理了。
如果要打印出所有数的组合，如123，132，213，231，312，321
则将listAll方法代码改为下面
public static void listAll(List<String> candidate, String prefix) {
if (candidate.isEmpty()) {
System.out.println(prefix);
}
for (int i = 0; i < candidate.size(); i++) {
//System.out.println("candidate is: " + candidate); // 此行代码便于理解递归
List temp = new LinkedList(candidate);// 转换为LinkedList便于安插和移动
listAll(temp, prefix + temp.remove(i));
}
}
打印结果为：
123
132
213
231
312
321
去掉注释后，更加容易理解，打印结果为：
candidate is: [1, 2, 3]
candidate is: [2, 3]
candidate is: [3]
123
candidate is: [2, 3]
candidate is: [2]
132
candidate is: [1, 2, 3]
candidate is: [1, 3]
candidate is: [3]
213
candidate is: [1, 3]
candidate is: [1]
231
candidate is: [1, 2, 3]
candidate is: [1, 2]
candidate is: [2]
312
candidate is: [1, 2]
candidate is: [1]
321
==================================================================================================
作者：欧阳鹏 欢迎转载，与人分享是进步的源泉！
转载请保留原文地址：http://blog.csdn.net/ouyang_peng
==================================================================================================
