N个集合，每个集合选一个元素组成新集合，打印所有结果

题目

给定n个集合，每个集合选一个元素组成新集合，打印所有结果。
例如，给定3个集合<1,2>,<3>,<4,5>，可所有结果为<1,3,4>，<1,3,5>，<2,3,4>，<2,3,5>

解析

从第一个集合的元素开始，依次选择第二个集合中的元素，直到最后一个集合，所有的元素构造了一个有向图无环结构。例子中集合构造的有向图如下图。从入度为0的节点出发，对有向无环图进行深度遍历，所有存在的路径就是需要打印的所有结果。

这里图的深度遍历，也可以理解为类似树的层级遍历，多叉树的层级遍历和多叉树所有路径。用递归回溯方法实现，入度为0的节点开始，向下一个层级深度遍历，每一个层级，节点遍历后回溯，然后继续遍历当前层级的下一个结点。如果是最后一个层级的节点，记录结果，遍历超过最后的层级，递归方法结束。

代码

//记录所有组合的结果
private List<List<Integer>> result = new LinkedList<>();
//回溯时暂存当前一个集合
private LinkedList<Integer> list = new LinkedList<>();
//递归回溯
public void printAllSets(List<List<Integer>> input, int row){
    //遍历超过最后的层级，递归方法结束
    if (row >= input.size()){
        return;
    }
    //当前row的层级
    List<Integer> in = input.get(row);
    //遍历当前层级的所有结点
    for (Integer i : in){
        list.add(i);//暂存当前节点
        //如果是最后一层，保存结果
        if (input.size() == row + 1){
            result.add(new LinkedList<>(list));
        }
        //从当前节点出发，递归遍历下一层级
        printAllSets(input,row + 1);
        //当前节点遍历结束后，进行回溯，然后准备遍历下一个节点
        list.removeLast();
    }
}